0

编写一个程序，提示用户输入一个整数，然后打印出直到该整数的所有素数。例如，当用户输入 20 时，程序应该打印 2 3 5 7 11 13 17 19 Recall that a number is a prime number if it is not visible by any number 除了 1 和它本身。

我正在尝试编写此程序，但遇到了困难，谁能告诉我如何编写此代码？这是我写的，但它是完全错误的。

import java.util.Scanner;

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

        System.out.print("Enter Integers: ");
        int x;
        int n = in.nextInt();

        for (int i = 2; i < n ; i++)
        {
            x = i;

            if (n % i != 0 && i % x != 0)
            {
                System.out.println(i);
            }
            x--;
        }
    }
}
4

2 回答 2

1

使用埃拉托色尼筛法计算小于或等于 N 的素数数。

% java PrimeSieve 25 素数 <= 25 的数目为 9

% java PrimeSieve 100 <= 100 的素数个数为 25

% java -Xmx100m PrimeSieve 100000000 素数<= 100000000的个数是5761455

% java PrimeSieve -Xmx1100m 1000000000 素数<= 1000000000的个数是50847534

110MB 和 1100MB 是您要分配给程序的内存量。如果您的计算机具有较少的内容，请将该数字变小，但它可能会阻止您解决非常大的 N 值的问题。

class PrimeSieve {
    public static void main(String[] args) { 
        int N = Integer.parseInt(args[0]);

        // initially assume all integers are prime
        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 i is prime, then mark multiples of i as nonprime
            // suffices to consider mutiples i, i+1, ..., N/i
            if (isPrime[i]) {
                for (int j = i; i*j <= N; j++) {
                    isPrime[i*j] = false;
                }
            }
        }

        // count primes
        int primes = 0;
        for (int i = 2; i <= N; i++) {
            if (isPrime[i]){ primes++; System.out.print(i+", ");}
        }
        System.out.println("\nThe number of primes <= " + N + " is " + primes);
    }
}
于 2013-09-12T18:59:24.893 回答
-1

使用此方法检查给定的 int 是否为素数。

public static boolean isPrime(int a)
{
    if ( a == 2)
        return true;
    int midpoint = Math.round(a/2);
    for(int i = 2; i < midpoint; i++)
    {
        if(a % i == 0)
            return false;
    }
    return true;
}

说明：循环遍历所有数字直到中点和模数，直到遇到 0 或没有。如果遇到 0 则返回 false 因为我们知道它不是素数，如果我们没有遇到零则返回 true 因为它是素数。
我们循环到中点，因为不需要进一步循环。

您可以通过在循环中实现它

for (int i = 2; i < n ; i++)
{
    if (isPrime(i))
    {
        System.out.println(i);
    }
}
于 2013-09-12T17:47:32.710 回答