소수 찾기
문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
n은 2이상 1000000이하의 자연수입니다.
입출력 예
n result
10 4
5 3
입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
----------------------------------------
(인터넷 검색/펌 포함)
int answer = 0;
int not_prime = 0;
int numOfPrime;
int n2 = (int)(Math.sqrt((double)n));
for(int i=2; i<=n; i++){
for(int j=2; j<=n2; j++){
if(i%j == 0 && i!=j) {
not_prime++;
break;
}
}
}
numOfPrime = n - not_prime - 1;
System.out.println("소수의 개수 : " + numOfPrime);
answer = numOfPrime;
return answer;
// => 값은 맞음. 시간 초과
int answer = 0;
int tot = 0;
boolean[] marked = new boolean[n + 1];
int nSqrt = (int) Math.sqrt(n);
for (int i = 2; i <= nSqrt; i++) {
if (!marked[i]) {
for (int j = i*i ; j < n + 1; j += i) {
marked[j] = true;
}
}
}
for (int i = 2; i < n + 1; i++) {
if (!marked[i] ) {
System.out.print(i + " ");
tot++;
}
}
System.out.println( );
answer = tot;
return answer;
// => 통과