Java/Coding Test

소수찾기 문제풀이

최고다최코딩 2023. 9. 18. 10:12
728x90

주어진 수까지의 정수 중 소수의 개수 반환

 

public int solution(int n) {

int answer = (n>=2)? 1: 0;

for(int i=3; i<=n;i+=2){

if(isPrime(i)){

answer++;

}

}

return answer;

}

public boolean isPrime(int n){

for(int i=2; i*i<=n;i++){

if(n%i==0){

return false;

}

}

return true;

}

n이 2일땐 소수는 2 자신을 갖고 1이하는 답은 0 이다.

소수를 찾을 때 3부터 찾고

효율성을 위해 소수인지 확인할 때는 i^2이 해당 수까지만 계산한다.