10001 번째 소수 번호 찾기 - 올바른 번호를 반환하지 않는 코드

Question

오해를 피하기 위해 저는 여기에서 새로 왔으며 아직 자바 초보자입니다. 10,001 번째 소수를 인쇄하는 코드를 작성하려고합니다. 코드는 현재 숫자가 2에서 9까지의 숫자로 나눌 수 있는지 확인한 다음 숫자의 제곱근이 정수인지 아닌지 확인합니다.

public static void main(String[] args){ 
    Integer Num , Counter; 
    Double Sqrt; //square root 
    Num=8; 
    Counter=4 ; 
    while(Counter<10001){ 
    Num++; 
    if ((Num%2!=0) && (Num%3!=0) && (Num%4!=0) && (Num%5!=0) && (Num%6!=0) && (Num%7!=0) && (Num%8!=0) && (Num%9!=0)){ 
    Sqrt = Math.sqrt(Num);  
    if(Sqrt%1!=0){ 
     Counter++; 
    } 
    } 
} 

System.out.println(Num); 
} 
} 

편집 : 더 이상 잘못된 정의를 사용하지만,이 새로운 코드가 더 출력이없고 내가 루프에 문제가 표시되지 않도록

나는 그것을 변경하지 않습니다. 아래의 다른 제안도 시도하지만이를 수정하는 방법을 알고 싶습니다.

public static void main(String[] args) 
    { 
int Num , Counter; 
double Sqrt; //square root 
Num=1; 
Counter=0 ; 

while(Counter<10001){ 
    Num++; 
    Sqrt = Math.sqrt(Num); 
    int i = (int)Sqrt; 
    while(i>1){ 
     if(Num%i==0){ //if the number is divisible then the loop is terminated and next number is tested 
     i=0; 
        } 
     i--; 
       } 

     if(i==1){ 
    Counter++; 
       } 
} 

System.out.println(Num); 
    } 
} 

감사합니다.

Answer 1

모든 숫자를 Math.sqrt(Num)에서 1로 테스트하기 때문에 새 버전이 작동하지 않습니다. 모든 숫자가 2로 줄어들지 않고 항상 1입니다. 항상 숫자가 모든 숫자에 들어가기 때문에 프로그램에서 소수가 소수라고 생각하지 않습니다. , 그리고 영원히 달린다.

while(i>0)을 while(i>1)으로 변경해야 작동합니다. if(i==0)을 if(i==1)으로 변경해야합니다. 또한 Num 및 Counter에 대한 귀하의 가치가 8과 4 인 이유를 잘 모르겠습니다. 나는 그들이 무엇을해야하는지 알아 내려고합니다.

Answer 2

소수의 정의가 잘못되어 작동하지 않습니다.

예를 들어, 숫자 437은 19 * 23이기 때문에 소수가 아니지만 현재 테스트를 통과합니다.

알고리즘에서 문제가되는 숫자가 으로 확인되지 않으면 검사 할 숫자의 제곱근까지의 소수를 검사해야합니다.

Answer 3

논리에 결함이 있습니다. 예를 들어, 숫자 143을 확인할 때 코드가 소수라고 생각합니다. 그러나 11 * 13 = 143이므로 실제로는 소수가 아닙니다. 소수를 나열하고 List를 통해 for-each 루프를 수행하는 것이 좋습니다.

List<Integer> primes = new ArrayList<Integer>(); 
int number = 2; 
while (primes.size() < 10001) { 
    boolean isPrime = true; 
    for (Integer prime : primes) { 
     if (number % prime == 0) { 
     isPrime = false; 
     break; 
     } 
    } 
    if (isPrime) { 
     primes.add(number) 
    } 
    number++; 
} 
System.out.println(primes.get(10000)); 

이것은 빠른 해결책은 아니지만 작동해야합니다 ... 테스트하지 않았습니다. 행운을 빕니다 :).

Answer 4

에라 토 스테 네스 (Eratosthenes)의 체를 기반으로 한 접근법을 사용합니다. 문제는 10001 프라임이 무엇인지 모르기 때문에 어레이를 만드는 데 얼마나 큰지 알지 못합니다. 큰 숫자를 생각해 볼 수는 있지만 10001 소수를 유지하기에 충분할 것으로 기대하지만, 너무 큰 경우 추가 작업을해야합니다. 근사치를 찾는데 도움이되는 수식이있을 수 있습니다.

다른 접근법은 더 작은 배열로 시작한 다음 필요한 경우 확장하는 것입니다. 1,000부터 1000까지의 숫자를 나타내는 부울 배열 (1000)부터 시작한다고 가정합니다. 체를 수행합니다 (2로 시작하고 목록에 2를 추가하고 배열에서 2의 배수를 모두 표시 한 다음 표시되지 않은 다음 값을 찾습니다). , 목록에 추가, 모든 배수 표시 등). 이것은 분명히 10001 번째 소수를 찾지 못할 것입니다. 따라서 부울 배열의 끝 부분에 도달했을 때이를 제거한 다음 "기본"변수를 변경하여 1001에서 2000 사이의 숫자를 나타냅니다. 이미 구축 한 소수의리스트를 살펴보고 모든 배수를 표시하십시오. 이제 모든 표시되지 않은 값은 소수입니다. 목록에 추가하고 배열을 지우고 배열이 이제 2001 ~ 3000의 숫자를 나타내도록 밑을 변경합니다. 소수 목록을 통해 배수를 표시하고 목록 크기가 10001에 도달 할 때까지 계속 이동합니다.

나는이 접근법이 다른 사람들과 비교해 얼마나 효율적인지 모르지만 직관적으로 모든 숫자를 하나씩 살펴보고 각 숫자를 약수로 확인하는 것보다 낫다고 생각합니다.

Answer 5

여기에서는 stream 클래스를 사용하여 const MAX (생성 된 요소 수)에 의해 제한된 소수의 시퀀스를 생성하는 또 다른 (압축) 방법을 찾을 수 있습니다 (생성 된 각 x에 대해 필터는 단, X로 나누어 : 자체에만 1로 나눌 수) 소수 :

public class PrimeNumbersSeq { 

    final private static Long MAX=10001l; 

    public static void main(String[] args) { 
    System.out.println(LongStream 
      .iterate(2, x -> x + 1) 
      .filter((i) -> LongStream.range(2, i) 
      .noneMatch(j -> i % j == 0)).limit(MAX) 
      .mapToObj(String::valueOf) 
      .collect(Collectors.joining(",", "[", "]"))); 
    } 
} 

출력 [2,3,5,7,11,13,17,19,23,29,31,37 , 41,43,47,53,59,61,67,71,73,79,83,89,97,101 ...