Java 素数生成器逻辑

Prime Number Generator Logic

提问by Shania

I am supposed to make a class PrimeNumberGeneratorwhich has a method nextPrimethat will print out all prime numbers up to a number the user inputs.

我应该创建一个类PrimeNumberGenerator，它有一个方法nextPrime可以打印出用户输入的所有质数。

Ex)

前任）

Enter a Number: 
20
2
3
5
7
11
13
17
19

Our teacher told us that we should use a nested forloop. I tried, but when I tried to make the inner (nested) loop, I got really confused.

我们的老师告诉我们应该使用嵌套for循环。我试过了，但是当我尝试制作内部（嵌套）循环时，我真的很困惑。

Here is my code: (I'm going to make a tester class later)

这是我的代码：（稍后我将制作一个测试员课程）

public class PrimeGenerator {

    private int num;
    boolean isPrime;

    public PrimeGenerator(int n)
    {
        num = n;
    }

    public int nextPrime (int num)
    {
        for (int i=2; i < num; i++) // The first prime number is 2 and the prime numbers only have to go up to a number the user inputs. 
        {
            for (int j = 3; j<=i/2; j+=2) // The next prime number is 3 and I attempted to loop through to get the next odd number.
            {
                if (num % i == 0) //if the number (upper limit) mod a "prime number" is 0, then that means that number is not really "prime" after all. 
                {
                    break;
                }
            }
        }

        return num;
    }

}

回答by rendon

Simple definition of a prime number: A number that is only divisible by one and by itself. By definition 1 isn't prime. Here is a brute force algorithm to determine if a number is prime or not.

质数的简单定义：只能被1和它自身整除的数。根据定义，1 不是素数。这是一个蛮力算法来确定一个数字是否为素数。

    boolean isPrime(int n)
    {
        for (int i = 2; i < n; i++)
            if (n % i == 0)
                return false;
        return true;
    }

回答by notArefill

Check this algorithm based on the sieve of Eratosthenes for prime numbers. Of course you need to adapt it to your program.

根据 Eratosthenes 的素数筛检查此算法。当然，您需要使其适应您的程序。

boolean isPrime[] = new boolean [N+1];
for (int i=2; i <=N; i++)
    isPrime[i] = true;

//mark non-primes <=N using Sieve of Eratosthenes
for (int i=2; i*i<=N; i++) 
{
    //if is a prime,then mark multiples of i as non prime 
    for (int j=i; i*j<=N; j++) 
    {
        isPrime[i*j] = false;
    }
}

for (int i=2; i<=N; i++) 
    if (isPrime[i])
        //Do something.......   

回答by Shreyas Patil

Try this code to generate prime number series

试试这个代码来生成素数系列

public class prime1 {

公共类prime1 {

public static void main(String[] args) {

    int max = 100;

    System.out.println("Generate Prime numbers between 1 and " + max);

    // loop through the numbers one by one
    for (int i = 1; i < max; i++) {

        boolean isPrimeNumber = true;

        // check to see if the number is prime
        for (int j = 2; j < i; j++) {
            if (i % j == 0) {
                isPrimeNumber = false;
                break; // exit the inner for loop
            }
        }

        // print the number if prime
        if (isPrimeNumber) {
            System.out.print(i + " ");
        }
    }

}

}

}

回答by Haakon L?tveit

There are two questions here that you have forgotten to ask:

这里有两个问题你忘记问了：

• Why does the nested loop make everything so complicated?
• What can I do to uncomplicate things again?

• 为什么嵌套循环让一切变得如此复杂？
• 我该怎么做才能让事情变得简单？

So let's play along with the question you actually asked, and then answer the first two questions.

所以让我们一起玩你实际问的问题，然后回答前两个问题。

What you want to do can probably be described as such: For every number, 1-n, where n is input by the user, print it if it's prime.

您想要做的可能可以这样描述：对于每个数字，1-n，其中 n 是由用户输入的，如果它是素数，则打印它。

Okay, so let's write up the pseudocode/logic here. It looks like Java, but it isn't. It's just meant to convey what we're going for:

好的，让我们在这里写下伪代码/逻辑。它看起来像Java，但它不是。它只是为了传达我们的目的：

int largestNumber = readIntegerFromKeyboard();

for all ints i from 1 to largestNumber {
    if(isPrime(i)) {
        println(i);
    }
}

So let's do this! But first, we need a laundry-list of all the things we need to do:

所以让我们这样做！但首先，我们需要一份我们需要做的所有事情的清单：

• read integer from keyboard
• loop over numbers
• check if the number is a prime
• print primes (with newlines)

• 从键盘读取整数
• 循环数字
• 检查数字是否为素数
• 打印素数（带换行符）

Let's just do the two easy things first. Reading the input and setting up the loop:

让我们先做两件简单的事情。读取输入并设置循环：

Scanner keyboard = new Scanner(System.in);
int largestNumber = keyboard.nextInt();

for(int i = 1; i <= largestNumber; ++i) {
    if(isPrime(i)) {
        System.out.println(i);
    }
}    

keyboard.close();

Okay, that seems simple enough. So far, everything here makes sense. It's easy to understand the logic. Now however, when we replace isPrime with actual logic, everything is about to get cluttered and hard to read.

好吧，这似乎很简单。到目前为止，这里的一切都是有道理的。很容易理解其中的逻辑。然而，现在当我们用实际逻辑替换 isPrime 时，一切都将变得混乱且难以阅读。

So let's write this code as easy to understand as possible. We will use no tricks to speed up the code. Readability and correctness are the onlytwo things we will care about. We will use the modulo operator to check if something is evenly dividable. Modulo is like integer division, except that it returns the remainder and not the result. so 7 / 2 = 2. 7 % 2 = 1, because there's one left over.

因此，让我们尽可能地编写易于理解的代码。我们不会使用任何技巧来加速代码。可读性和正确性是我们唯一关心的两件事。我们将使用模运算符来检查某物是否可均匀整除。Modulo 类似于整数除法，除了它返回余数而不是结果。所以 7 / 2 = 2. 7 % 2 = 1，因为还剩下一个。

Scanner keyboard = new Scanner(System.in);
int largestNumber = keyboard.nextInt();

for(int i = 1; i <= largestNumber; ++i) {
    // checks if the number is a prime or not
    boolean isPrime = true;
    for(int check = 2; check < i; ++check) {
        if(i % check == 0) {
            isPrime = false;
        }
    }
    if(isPrime) {
        System.out.println(i);
    }
}    

So the good news is, this works. The bad news is, this is harder to read than necessary. And it's not a lot we can do here. When I wrote this up, I made several stupid mistakes, mixing up the variables. Maybe I'm stupid. So maybe I should in that case write stupid-proof code. ;) You on the other hand is not stupid. But you may work with me, who isstupid, so you kind of have to write stupid-proof code yourself, so that you can productively work with me.

所以好消息是，这是有效的。坏消息是，这比必要的更难阅读。我们在这里能做的并不多。当我写这篇文章时，我犯了几个愚蠢的错误，混淆了变量。也许我很傻。所以也许我应该在这种情况下编写防愚蠢代码。;) 另一方面，你并不愚蠢。但是你可能会和我一起工作，谁是愚蠢的，所以你必须自己编写防愚蠢的代码，这样你才能和我一起高效地工作。

The big problem is that we have this massive loop in the middle of the other loop. This is what tripped me up. I referred to the wrong loop variable. But why do we need a loop in a loop? Wasn't it much more comfortable to read:

最大的问题是我们在另一个循环的中间有这个巨大的循环。这就是让我绊倒的原因。我引用了错误的循环变量。但是为什么我们需要一个循环中的循环呢？读起来不是更舒服吗：

if(isPrime(i)) {
    System.out.println(i);
}

Instead of that whole mess? Your professor pointed out the nested loops. But it threw you off. Instead, just write the isPrime method. And the fact is, that this is true for every single instance of nested loops I have ever come across.. So let's see how that would look instead:

而不是那一团糟？您的教授指出了嵌套循环。但它让你失望了。相反，只需编写 isPrime 方法。事实是，这对于我遇到的每个嵌套循环实例都是正确的..所以让我们看看它会是什么样子：

class Homework {
    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int largestNumber = keyboard.nextInt();

        for(int i = 1; i <= largestNumber; ++i) {
            if(isPrime(i)) {
                System.out.println(i);
            }
        }
        keyboard.close();
    }

    /**
     * Checks is a positive integer is a prime number
     */
    public static boolean isPrime(int number) {
        for(int check = 2; check < number; ++check) {
            if(number % check == 0) {
                return false;
            }
        }
        return true;
    }
}

That to me is a whole lot easier to read. Not because the logic got easier, but because the onlythingI had to care about was either:

对我来说，这更容易阅读。不是因为逻辑变得更容易了，但由于只有一点我不得不关心要么是：

• Checking all the numbers and printing the correct ones, or
• how to check that a number is a prime.

• 检查所有数字并打印正确的数字，或
• 如何检查一个数是否为素数。

Since these two separate things are now apart, you have much less to think about at once. Rejoice, for you have just done a proper abstraction. This makes your code easier to understand, because it separates out the two concerns. This is a key way of making larger projects. You take difficult things and do them by themselves. Then you can test them by themselves, and use them by themselves.

由于这两个独立的事情现在分开了，因此您可以立即考虑的事情少得多。庆幸，因为你刚刚做了一个适当的抽象。这使您的代码更易于理解，因为它将两个关注点分开。这是制作大型项目的关键方法。你把困难的事情自己做。然后你可以自己测试它们，然后自己使用它们。

(Now I only have to await the downvotes for answering a question you didn't explicitly ask...)

（现在我只需要等待投票来回答你没有明确提出的问题......）

回答by Praveen Kumar

public class PrimeNumberGeneration {

公共类 PrimeNumberGeneration {

public static void main(String[] args) {
    // TODO Auto-generated method stub

    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();

    ArrayList<Integer> primeNumbers = new ArrayList<Integer>();
    primeNumbers.add(2);
    System.out.println(2);

    no_loop:
    for(int no=3; no<=n; no+=2){
        for(Integer primeNumber: primeNumbers){
            if((no%primeNumber)==0){
                continue no_loop;
            }
        }
        primeNumbers.add(no);
        System.out.println(no);
    }

}

}

}

回答by Rakesh Gupta

To generate prime number simply loop through a given number and check if that number is prime or not. For efficient prime number generation IsPrime method must be very efficient and fast. So here is code to check if given number is prime or not very efficiently.

要生成素数，只需遍历给定的数字并检查该数字是否为素数。对于有效的素数生成，IsPrime 方法必须非常高效和快速。所以这里有代码来检查给定的数字是否是质数或不是很有效。

public static boolean IsPrime(int n) {

    if (n > 2 && n %2 == 0){
        return false;
    }
    int top = (int)Math.sqrt(n)+1;
    for (int i=3;i<top;i+=2){
        if (n%i==0){
            return false;
        }
    }
    return true;
}

Here is the code that will generate prime number between 1 and given number.

这是将在 1 和给定数字之间生成素数的代码。

 public class GeneratePrimeNumber {
    public static void main(String[] args) {
    System.out.println("Enter number to get prime number");
    int n = new Scanner(System.in).nextInt();
        for (int j=0;j<n;j++){
            if (IsPrime(j)){
                System.out.print(j + " ");
            }
        }

    }
 }

回答by Akash Das

import java.util.regex.Matcher;
import java.util.regex.Pattern;

import javax.xml.soap.Node;

public class mainone {

 public static void main(String args[]){

    int[] primenumber=new int[13];

    for(int a=2,j=0;a<=14;a++,j++){
        primenumber[j]=a;

    }

    for(int b=1;b<13;b++){
        int d=primenumber[b];
        if(d%2==0){
            primenumber[b]=0;
        }

        for(int c=2;c<13;c++){
            int e=primenumber[c];
            if(e>0){
                for(int f=c+1;f<13;f++){
                    int g=primenumber[f];
                    if((g>0)&(g%e==0)){
                        primenumber[f]=0;
                    }


                }
            }
        }
    }


    for(int j=0;j<13;j++){
        System.out.println(primenumber[j]);
    }
     }

 }

回答by Jathin Jathin

package test;

import java.util.Scanner;

public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner reader = new Scanner(System.in);  // Reading from System.in
        System.out.println("Please Enter number you wanted prime number to be generated");
        int n = reader.nextInt();
        reader.close();

        Prime t1 = new Prime();
        for (int i = 2; i <= n; i++) {
            t1.x(i);
        }
    }

    public void x(int n) {
        // TODO Auto-generated method stub
        // TODO Auto-generated constructor stub
        int k = n - 1;
        int f = 0;
        if (n == 2) {
            f = 1;
        }
        for (int i = 2; i <= k; i++) {
            if (n % i == 0)
                break;
            else if (k == i) {
                f = 1;
            }
        }
        if (f == 1) {
            System.out.println("is prime" + n);
        }

    }
}

回答by danish ahmed

Check out my code:

看看我的代码：

import java.util.Scanner;

public class c4 {

        public static void main(String[] args) {
            Scanner sn = new Scanner(System.in);

            System.out.println("Enter number");

            int num = sn.nextInt();

            if (num==1){
                System.out.println("Nor Prime Neither Composite");
            }
            for (int i=2;i<num;i++){
                int n=num%i;

                if (n==0){
                    System.out.println("It is a composite number");
                    break;
                }
               else{
                   System.out.println("it is a prime number");
                   break;
               }
           }
       }
    }

回答by artlovan

I know the question is for a while out here but since no one posted java8/stream approach solution, here is one of the possible ways.

我知道这个问题有一段时间了，但由于没有人发布 java8/stream 方法解决方案，这里是一种可能的方法。

Gist can be forked here.

要点可以在这里分叉。

Print output: [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

打印输出：[1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

import java.util.*;
import java.util.stream.Stream;

import static java.util.stream.Collectors.toList;


public class PrimeNumber {

     /**
     * Java 8 / Lambda approach to generate Prime number.
     * Prime always start to look from number 1.
     * @param series Number of how many Prime number should be generated
     * @return List holding resulting Prime number.
     */
    public static List<Integer> generate(int series) {
        Set<Integer> set = new TreeSet<>();
        return Stream.iterate(1, i -> ++i)
                .filter(i -> i %2 != 0)
                .filter(i -> {
                    set.add(i);
                    return 0 == set.stream()
                            .filter(p -> p != 1)
                            .filter(p -> !Objects.equals(p, i))
                            .filter(p -> i % p == 0)
                            .count();
                })
                .limit(series)
                .collect(toList());
    }

    // Let's test it!
    public static void main(String[] args) {
        List<Integer> generate = PrimeNumber.generate(20);
        System.out.println(generate);
    }
}