public class 소수구하기 {

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  
  int num = 3000000;
  int not_prime = 0;
  int numOfPrime;
  int i;
  int j;
  
  int 제곱근값 = (int)(Math.sqrt((double)num));

  for(i=2; i<=num; i++){
   for(j=2; j<=제곱근값 && j<i; j++){
    if(i%j == 0){
     not_prime++;
     break;
    }
   }
  }
  
  numOfPrime = num - not_prime -1;
  System.out.println("소수의 개수 : " + numOfPrime);
 }
}


문제점 : 숫자가 200만 넘어가면 느림



코드도장 가보니까 1000만 이하 소수 1.82초만에 구하던데


내건 1000만에 7초정도 걸리는듯


힌트좀 어떤 방법을 써야되나