編寫一個方法來查找素數

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(); 

     } 

    } 
}