1

我正在编写一个代码，将 2 到 1000 的所有素数写入一个名为 primes.txt 的文件中。出于某种原因，我无法找出解决此问题的正确方法。

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;

public class Problem6 {

    /**
     * @param args
     * @throws FileNotFoundException 
     */
    public static void main(String[] args) throws FileNotFoundException {
        PrintWriter prw = new PrintWriter("primes.txt");
        for (int i = 2; i <= 1000; i++){
            if (checkIfPrime(i) == true){
                System.out.println(i);
                prw.println(i);
            }
        }
    }

    public static boolean checkIfPrime (int num){
        boolean isPrime = true;  
        for (int i = 2; i <= 1000; i++){
            if ( num % i == 0 ){
                isPrime = false;
            }
        }

        return isPrime;
    }
}

我只是不知道该怎么做...请帮助谢谢！

4

5 回答 5

6

当您将第一个数字 , 2,传递给 时会发生什么checkIfPrime？它将取 2 除以 2 的余数，即 0，错误地声称这2不是素数。

您需要在实际到达之前停止测试余数num。在到达之前停止你的ifor 循环。（实际上，您可以在达到 的平方根后停止）。inuminum

for (int i = 2; i < num; i++){

甚至

for (int i = 2; i <= Math.sqrt(num); i++){

如果您喜欢冒险，可以尝试实施埃拉托色尼筛法，它将所有合数标记为任意限制（在此问题中为 1000）。然后你只需打印出其余的数字——素数。

于 2013-09-06T22:20:30.920 回答
3

通过仅检查素数的除法，可以更快地进行计算。任何非素数都可以被某个小于自身的素数整除。

    static List<Integer> primes = new ArrayList<Integer>();

public static void main(String[] args) {
    for (int i = 2; i < 10000; i++) {
        if(checkPrime(i)){
            primes.add(i);
        }
    }
    System.out.println(primes);
}

private static boolean checkPrime(int n) {
    for (Integer i : primes) {
        if(i*i > n ){
            break;
        }else if(n%i==0 )
            return false;
     }
    return true;
}
于 2013-09-06T23:22:40.963 回答
2

for将您的条件更改checkIfPrime(int num)为

for (int i = 2; i < num; i++) {

BTWif (checkIfPrime(i) == true){可以写成if (checkIfPrime(i)){

于 2013-09-06T22:19:58.080 回答
1

如果一个数num不能被任何其他大于 1且小于num的数整除，则该数是素数。你的代码在哪里？:-)

于 2013-09-06T22:20:04.247 回答
0

以下是如何在2-3-5-7 轮上“硬编码”一个递增的 Eratosthenes 筛，以打印最高1000的素数。在类 C 的伪代码中，

primes_1000()
{
   // the 2-3-5-7 wheel
   int wh[48] = {10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,
                  2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2};
   // core primes' multiples, each with its pointer into the wheel
   int m[7][4] = { {1,11,11,11*11}, {2,13,13,13*13}, {3,17,17,17*17},
                   {4,19,19,19*19}, {5,23,23,23*23}, {6,29,29,29*29},
                   {7,31,31,31*31} };    // 23*23 = 529 
   int i=1, p=11, k=0;
   print(2); print(3); print(5); print(7);
   p = 11;             // first number on the wheel - the first candidate
   do {
      // the smallest duplicate multiple is 121*13, ==> no dups below 1000!
      for( k=0; k < 7; ++k) {
         if ( p == m[k][3] ) {             // p is a multiple of m[k][1] prime:
            m[k][2] += wh[ m[k][0]++ ];    //   next number on the wheel
            m[k][3]  = m[k][1] * m[k][2];  //   next multiple of m[k][1] 
            m[k][0] %= 48;                 //   index into the wheel
            break;
         }
      }
      if (k == 7) {    // multiple of no prime below 32 -
          print(p);    //   - a prime below 1000!   (32^2 = 1024)
      }
      p += wh[i++];    // next number on the candidates wheel
      i %= 48;         // wrap around to simulate circular list
   } while ( p < 1000 );
}

对于低于500的素数，只需要维护 4 个筛变量，对于高于轮子固有素数2,3,5,7的附加核心素数{11,13,17,19}。

（另请参阅打印从 1 到 100 的素数）。

m是基本素数及其在轮子上的倍数的字典 ( multiplesOf(p) = map( multiplyBy(p), rollWheelFrom(p) )，每个都有自己的轮子索引。它实际上应该是一个优先级队列，按倍数的值最小排序。

对于真正的无界解决方案，可以维持单独的素数供应，以在候选中达到下一个素数的平方时逐个素数扩展字典素数。

于 2014-02-19T14:58:52.047 回答