[BOJ 1978] 소수찾기 (에라토스테네스의 체 란?)

 

소수란?

약수가 1과 자기자신만을 갖는 수를 의미한다.

즉, 아무수에도 나누어 떨어지지않는 수

 

에라토스테네스의 체란?

- 주어진 범위 내의 모든 소수를 찾는 데 사용

- 2부터 시작하여 배수들을 제거해나가며 소수를 찾는 방법

=> 그런데 2~n까지 소수를 구한것이 아니라, N이 소수인가?를 판별하는 문제이기에 효율성이 떨어지지않을까 생각된다.

 

소수판정법

- 2부터 루트(N)까지를 모두 나눠본다.

- 루트(N)이상을 하는것은 무의미하기때문

 

 

package math_problem

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

func RunBoj1978(){
	scanner := bufio.NewScanner(os.Stdin);
	scanner.Scan()
	N,_ := strconv.Atoi(scanner.Text());

	if N == 0 {
		return ;
	}

	scanner.Scan()
	input := strings.Split(scanner.Text(), " ");

	result := 0;
	for i := 0; i < N; i++ {
		target,_ := strconv.Atoi(input[i]); 

		if(isPrime(target)){
			result++;
		}
	}

	fmt.Println(result);
}

func isPrime(num int) bool{
	if num == 1 {
		return false;
	}

	max := int(math.Sqrt(float64(num)));

	for i := 2; i <= max; i++ {
		if(num%i==0){
			return false;
		}
	}

	return true;
}