计算非负数下的素数数量 - JAVA

I wrote out code to find the number of prime numbers under a non-negative number, not sure what is wrong with this code: - When I n = 10, my output is 4 which is correct. (2,3,5,7) - Prime numbers under 10 - When I n = 10000, my output is 3334, while it should be 1229. Not sure where this code is going wrong and I have spent a lot of time analyzing it.

我写出代码来查找非负数下的素数数，不知道这个代码有什么问题： - 当我n = 10时，我的输出是4，这是正确的。（2,3,5,7） - 素数低于10 - 当我n = 10000时，我的输出是3334，而它应该是1229.不确定这段代码出错的地方我花了很多时间分析它。

public static void main (String [] args) {

public static void main（String [] args）{

    int n = 10000;
    int counter = 0;

    if (n <= 2) {
            System.out.println("0 prime numbers"); }

    if (n == 3) {
         System.out.println("1 prime number"); }

    counter+=2; //accounts for prime numbers 2 and 3

    for (int x = 4; x < n; x++) { 

            //Started at 4 since I have already checked for 2 and 3
            if (isPrime(x) == true) {
                counter = counter + 1;  }
    }

      System.out.println("The number of prime numbers are " + counter); }

  public static boolean isPrime (int x) {
    if (x % 2 == 0 || x % 3 == 0) {
        return false; }
    return true;
}

2 个解决方案

#1

The concept of Prime number: The prime numbers are the natural numbers greater than one that are not products of two smaller numbers.

素数的概念：素数是大于1的自然数，不是两个较小数的乘积。

Maybe this is what you want:

也许这就是你想要的：

public static boolean isPrime(List<Long> primes, long number) {

    if(number < 2) return false;

    for (Long prime : primes) {
        if (number % prime == 0) return false;
    }

    return true;
}

public static void main(String[] args) {
    List<Long> primes = new ArrayList<>();
    long max = 10000;
    long num = 2;
    while(num < max) {
        if(isPrime(primes, num)) {
            primes.add(num);
        }
        num++;
    }
    System.out.println("count: " + primes.size());
    System.out.println("primes: " + primes);
}

the output of code above:

以上代码的输出：

count: 1229

数：1229

primes: [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, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, ....

素数：[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,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227 ，229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373 ，379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523 ，541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683 ，691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859 ，863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013，....

9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]

9613,9619,9623,9629,9631,9643,9649,9661,9677,9679,9689,9697,9719,9721,9733,9739,9743,9749,9767,9769,9781,9787,9791,9803,9811， 9817,9829,9833,9839,9851,9857,9859,9871,9883,9887,9901,9907,9923,9929,9931,9941,9949,9967,9973]

#2

Replace your isPrime function with the following:

用以下内容替换isPrime函数：

boolean isPrime(int n) {
  //check if n is a multiple of 2
  if (n%2==0) return false;
  //if not, then just check the odds
  for(int i=3;i*i<=n;i+=2) {
    if(n%i==0)
        return false;
  }
  return true;
}

I got this solutions from here. Basically, if a number is not divisible by two, it won't be divisible by any other even number. So, just check to see if it's divisible by any odd number. This will produce the correct answer and cut your search time in half.

我从这里得到了这个解决方案。基本上，如果一个数字不能被2整除，它将不能被任何其他偶数整除。所以，只需检查它是否可以被任何奇数整除。这将产生正确的答案，并将您的搜索时间减少一半。

#1