for (long i : list) { boolean isNotPrime = false; for (int j = 2; j * j <= i; j++) { if (i % j == 0) { isNotPrime = true; break; } }
if (!isNotPrime) { ++answer; } }
return answer; }
private List<Long> getSumList(int[] nums){ List<Long> list = new ArrayList<Long>();
int arrayLength = nums.length; for (int i = 0; i < arrayLength; i++) { for (int j = i + 1; j < arrayLength; j++) { if (j == arrayLength - 1) { break; }
for (int k = j + 1; k < arrayLength; k++) { list.add((long) (nums[i] + nums[j] + nums[k])); } } }
publicintsolution(int n){ boolean[] prime = newboolean[n+1];
prime[0] = true; prime[1] = true;
for (int i = 2; (i * i) <= n; i++) { if (!prime[i]) { for (int j = i * 2; j <= n; j += i) { prime[j] = true; } } }
int answer = 0; for (boolean is : prime) { if (!is) { answer++; } }
return answer; }
흐름
에라토스테네스의 체로 해결
n까지의 숫자중 0과 1은 소수가 아니므로 true 할당
2부터 루트n 까지 반복하면서 배수들에 true 할당
소수 판별한 배열 prime을 loop 돌면서 false 인 경우에만 갯수 추가
끝
부연 설명
1
for (int i = 2; (i * i) <= n; i++)
입력받은 수 n이 합성수 인 경우 $$n = a * b$$ 로 나타낼 수 있다. 이 때 a와 b 중 큰거나 같은 수를 a, 작거나 같은 수를 b라고 가정하면 b가 a보다 작으므로 $$ a * a >= a * b $$ 이고 $$ n = a * b $$ 이므로, 큰 수 a의 제곱일 경우 $$ a^2>=n $$ 처럼 된다. 이를 치환하면 $$ a>=\sqrt{n} $$ 이 되므로 a의 최솟값은 $$ \sqrt{n} $$ 이 된다. 그리고 b는 $$ a >= b $$이므로 b의 최댓값은 $$ \sqrt{n} $$ 이 된다. 고로 n이 소수가 아닌 합성수라면 a의 와 b의 합성수로 이루어 짐을 알 수 있으므로, $$ \sqrt{n} $$ 까지만 반복하면 소수임을 판별할 수 있다.
ex) 입력받은 수 n이 50일 경우 $$ \sqrt{50} $$ = 7.071067811865475….이므로, 7.071067811865475… 을 기준으로 50의 약수 {1,2,5,10,25,50}을 나누면 b = {1, 2, 5}, a = {10, 25, 50} 이므로 b만 검사하면 50이 소수 인지 아닌지 알 수 있다.
1
for (int j = i * 2; j <= n; j += i)
원래는 i보다 작은 수인 경우 이미 이전에 작은 수 * i에서 삭제된 상태이므로 i * i인 게 맞으나, i의 값이 너무 클 경우 문제가 될 수 있으므로 $$ i * 2 $$ 로 설정한다. 물론 이 문제에선 100만 까지로 한정되어 있으므로 $$ i * i $$ 를 해도 문제는 없다.
