编写一个方法来查找素数

Question

我正在尝试编写一个程序，该程序使用谓词方法来查找1-100之间的所有素数。我知道现在有更有效的方法来寻找素数，但是现在我想使用强力策略并尝试所有可能的组合。

现在的程序就是这样，只是打印真假10000次，但我希望我的程序只打印数字，如果它们是素数。所以在程序完成后，我会得到一个介于1到100之间的素数列表。

1.我的程序是否正确？ 2.什么是最好的建议改变我的程序，以便它列出1-100之间的所有素数。

import acm.program.*; 
public class PrimeNumbers extends ConsoleProgram{ 
public void run(){ 

    for (int i =1; i <= 100, i++){ 
     for (int j =1; j<= 100; j++){ 
      println(yesPrime(i, j)); 
     } 
    } 
    } 

private boolean yesPrime (int n, int k){ 
     return (n % k == 0) 

     } 
    } 
    } 

Answer 1

您不检查素数。您正在测试从1到100两个数字的所有10,000个组合，以查看第二个数字是否均匀分配。

但它很可能是正确的。

伪代码为你想要做什么：

for each number n from 2:100 
    for each divisor d from 2:n-1 
     test to see if d divided n evenly 
    end for 
    if no values of d other than n divided n evenly 
     print "n is prime" 
end for 

一对夫妇的优化，为您思考的：

• 你的内环只需要上去的sqrt（N）。 （为什么？）
• 而不是所有的数字，你只需要检查它是否划分你已经找到均匀的奇素数。 （为什么？）

玩得开心！

Answer 2

那么，您将返回yesPrime的比较，然后将该比较的结果打印在run中。猜猜输出是什么。

考虑到这是一项任务，我想给你一个提示，而不是答案。

检查yesPrime的结果。如果为true，则打印该号码并跳出循环。

Answer 3

我会做一个功能，就像你的yesPrime功能。这只需要一个数字，然后检查该数字是否为总数。

喜欢的东西

boolean yesPrime(int n) 
{ 
    // check to see if n is divisble by numbers between 2 and sqrt(n) 
    // if the number is divisible, it is not prime, so return false 
    // after the loop has checked all numbers up to sqrt(n), n must be prime so return true 
} 

然后在你的主程序，遍历数字1到100，并呼吁yesPrime每个号码。如果结果为真，则打印该号码。

我的努力是编程的一个目标是将问题分解成更小的子问题。通过编写一个函数来测试素数，可以避免在一个函数中使用嵌套循环，这可能更难理解。

Answer 4

对于初学者，您需要检查从2开始的素数。而且您不会针对所有100个数字进行检查，只是将每个数字作为从2到数字1的一个因子。每个数字都可以被整除由1和本身。

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

private static boolean checkPrime(int k) { 

    for (int i = 2; i < k; i++) { 
//check if the number is divisible by any number starting from 2 till number -1.If it is, it is not a prime number 
     if (k % i == 0) 
      return false; 
    } 
// return true if the number is not divisible by any number from 2 to number -1 i.e. it s a prime number. 
    return true; 
} 

Answer 5

使用埃拉托色尼的筛子：

public static void main(String[] args) { 

    int n = 100; // the max number for test 

    // Sieve of Eratosthenes 
    boolean[] sieve = new boolean[n + 1]; 
    for (int i = 2; i <= n; i++) { 
     sieve[i] = true; 
    } 
    for (int i = 2; i <= n; i++) { 
     if (sieve[i] != false) { 
      for (int j = i; j * i <= n; j++) { 
       sieve[i * j] = false; 
      } 
     } 
    } 

    // Print prime numbers 
    for (int i = 0; i <= n; i++) { 
     if (sieve[i]) { 
      System.out.println(i); 
     } 
    } 

} 

Answer 6

想想这个逻辑
所有数能被2整除不是素数，因此您可以通过2
增加你的电话号码，如果号码不由素数整除那么它是一个素数

试试这个代码

public static void main(String[] args) throws IOException 
    { 
     int[] prime=new int[50]; //array to store prime numbers| within 1 to ==> prime numbers will be <=n/2 here n=100 
     int i=1;  //index for "num" array 
     int j=1;  //index for storing to "prime" array 
     int k=1;  //index for browsing through prime array 
     prime[0]=2;  // setting the first element 
     int flag=1;  // to check if a number is divisibe for than 2 times 
     for(i=3;i<=100;i+=2) { 
      for(k=0;prime[k]!=0;k++) //browsing through the array to till non zero number is encountered 
      { 
       if(i%prime[k]==0) flag++; //checking if the number is divisible, if so the flag is incremented 
      } 
      if(flag<2) 
      { 
       prime[j++]=i;    // if the flag is still 1 then the number is a prime number 
      } 
      flag=1; 
     } 
     System.out.println(Arrays.toString(prime)); //a short way to print an array 
     } 

Answer 7

在给定的范围内找到素数很容易 /* 请实现此方法以返回给定范围（包含）中的所有素数列表。质数是一个自然数，它有两个不同的自然数除数，它们分别是1和素数本身。第一素数是：2，3，5，7，11，13 */

public void getPrimeNumbers(int st, int en){ 
    // int st=1, en=100; 
    for(int i=st;i<=en;i++) 
     if((i%2!=0) && (i%1==0 && i%i==0)) 
      System.out.println("Yes prime");  
} 

Answer 8

public static void main(String[] args) { 

    boolean isPrime = true;    //set isPrime to true 

    for (int i = 2; i<100;i++){   // consider i is increasing number 

     for (int j=2; j<i; j++)   //j is divisor & must be less than 
             //i and increasing after each iteration 
     { 
      if((i % j)== 0){    // if i gets divisible by 
             // any increasing value of j from 2 
             //then enters in this case and makes value 
             //nonPrime 
       isPrime=false;  //changes value 
      break;     //breaks "for loop of j" 
     } 
      }    //ends "for loop of j" 
     if(isPrime)   // if case wont work then number is prime 
     { 

      System.out.println(i + " is Prime"); 
     } 
     isPrime = true;  //sets isPrime to default true. 
    } 
    } 

Answer 9

Scanner reader = new Scanner(System.in); 
    System.out.println("Enter the a number"); 
    int num = reader.nextInt(); 
    int counter = 0; 
    int root = 0; 
    boolean prime_flag; 

    if (2 <= num) { 
     // 2 is the only even prime number 
     counter++; 
    } 

    for (int i = 3; i < (num + 1); i++) { 

     // test only for odd number 
     if (i % 2 != 0) { 
      prime_flag = true; 
      root = (int) (Math.sqrt(i) + 1); 

      for (int j = 3; j < (root + 1); j++) { 
       if ((i % j == 0) && (i != j)) { 

        prime_flag = false; 
        break; 
       } 
      } 

      if (prime_flag) { 
       counter++; 
      } 

     } 

    } 

    System.out.println("Count of prime numbers upto " + num + " is " 
      + counter); 

Answer 10

随着较不复杂的方法，我们可以这样做：

import java.math.BigInteger; 

public class PrimeNumbers { 

    public static void main(String[] args) { 
     BigInteger min = new BigInteger("2"); 
     BigInteger max = new BigInteger("100"); 

     while(min.compareTo(max) < 0){ 

      System.out.println(min); 
      min = min.nextProbablePrime(); 

     } 

    } 
}