1

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

现在程序原样只打印 10,000 次 true 或 false ，但我希望我的程序只打印素数的数字。所以在程序完成后，我将得到一个 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)

       }
    }
  }
4

11 回答 11

10

你不是在检查素数。您正在测试从 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)。（为什么？）
  • 而不是所有的数字，您只需要检查它是否将您已经找到的奇质数均分。（为什么？）

玩得开心！

于 2013-05-22T03:24:43.667 回答
3

使用 Eratosthenes 的筛子：

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

}
于 2013-05-22T04:24:56.903 回答
1

好吧，您从 中返回一个比较yesPrime，然后在 中打印该比较的结果run。猜猜输出会是什么。

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

检查结果yesPrime。如果为真，则打印数字并跳出循环。

于 2013-05-22T03:26:43.033 回答
1 
    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);
于 2015-03-10T17:32:18.247 回答
0

在给定范围内轻松找到素数 /* 请实现此方法以返回给定范围（包括）内所有素数的列表。素数是一个自然数，它恰好有两个不同的自然数除数，即 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");      
}
于 2014-01-10T04:33:17.937 回答
0

对于初学者，您需要检查从 2 开始的素数。并且您不需要针对所有 100 个数字进行检查，只需将每个数字作为从 2 到 (number-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;
}
于 2013-05-22T03:42:02.500 回答
0

我会做一个函数，就像你的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。如果结果为真，则打印该数字。

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

于 2013-05-22T03:34:27.087 回答
0 
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. 
    }
    }
于 2014-02-04T18:37:06.590 回答
0

想想这个逻辑
所有能被 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
        }
于 2013-10-24T12:33:26.990 回答
0

使用不太复杂的方法，我们可以做到这一点：

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

        }

    }
}
于 2017-07-18T11:49:44.507 回答
0

这是我查找素数的解决方案。

public class PrimeNumberFinder {

    public boolean isPrime(int number) {
        return number > 1 && IntStream.rangeClosed(2, number / 2)
                .noneMatch(value -> number % value == 0);
    }
}
于 2018-05-02T18:21:20.037 回答