java 区间内的素数

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

想要改进这个问题吗？通过编辑这篇文章来更新问题，使其仅关注一个问题。

2 年前已关闭。

Answer 1

使用 isProbablePrime，它比您编写的任何实现都要快。

Answer 2

在函数内部执行 for 循环

public static List<Integer> getPrimeNumbers(int lowerBound, int upperBound){
    ArrayList<Integer> primeNumber = new ArrayList<>()
    // loop over all numbers in the range and add the number to primeNumber list if it is a prime.
    for (int i = lowerBound, i <= upperBound, i++){
        if isPrime(i){
            primeNumber.add(i);
        }
    }
    return primeNumber;
}

// function to check if a number is prime
public static boolean isPrime(int num){
    boolean flag = false;
    for (int i = 2; i <= num / 2; ++i) {
        // condition for nonprime number
        if (num % i == 0) {
            flag = true;
            break;
        }
    }
    return flag;
}

Answer 3

对于较小的数字，您可以使用埃拉托色尼筛法。对于较大的，这个方法不起作用......

private static boolean sieve[];

private static void eratosthenesSieve(int maxN)
{
     sieve = new boolean[maxN+1];
     
     Arrays.fill(sieve, true);//sets all elements of the given array to true
     sieve[0] = false;// 0 isn't prime
     sieve[1] = false;// 1 isn't prime
     
     for (int i = 2; i <= maxN; i++) {//loop starts at 2 because we already know that 0 and 1 are false...
         if (sieve[i]) {//checks if the current number is prime
              for (int j = i*2; i <= maxN; j+=i) {
                  sieve[j] = false;//sets the multiples of current prime number to false
              }
          }
     }
}

public static void main(String... args)
{
     int min = 0, max = 0;
     Scanner sc = new Scanner(System.in);
     
     System.out.println("Enter the range of Prime numbers seprated with a space");
     min = sc.nextInt();
     max = sc.nextInt();
     
     eratosthenesSieve(max);
     do{//loop prints in descending order, if you want ascending change the condition to min++<max, check sieve[min] instead of sieve[max] and print min instead of max
         if(sieve[max]){
             System.out.println(max);
         }
     }while(max-->min);//loop is min and max inclusive if you want only max exclusive, change this to while loop with same condition, if you want both exclusive change this to while loop with --max>min condition
 }
     

Answer 4

我将包装一个名为 isPrime(int) 的方法，其中我将按照 @巴拉库加夫。我在另一篇文章中提供了答案，您可以在其中看到它的实际效果。

采用这种方法的原因是，可以为您的最佳情况建立一种方法，该方法可以重用于检查其他类型素数的方法；就像索菲·热尔曼素数一样。

public boolean isPrime(int n) {
    if (n < 2) return false;
    BigInteger bigInt = BigInteger.valueOf(n);
    return bigInt.isProbablePrime(100);
}

/*
 * A prime p is said to be a Sophie Germain prime if both p and 2p+1 are prime
 */
public boolean isSophieGermainPrime(int n) {
    return isPrime(n) && isPrime(2*n + 1); // reusing my base method to implement a new variant
}

计算范围内的素数也可以这样说...

public List<Integer> getPrimeNumbers(int min, int max) {
    public List<Integer> primes = new ArrayList<>();
    for (int n = min; n <= max; n++) {
        if (isPrime(n)) {
            primes.add(n);
        }
    }
    return primes;
}

更新：
我会将参数的数据类型从 int 更改为 long。这使我能够计算 mersennePrimeForRange(1, 1000000000) 范围内的前九个 Marsenne 素数

/*
 * A Mersenne prime (Mn) is a prime number that is one less than a power p of two
 * where exponent p must be prime as well.
 */
public static void mersennePrimeForRange(long min, long max) {
    for (long p = min; p <= max; p++) {
        if (isPrime(p)) {
            long mn = (long) Math.pow(2, p) - 1;
            if (isPrime(mn)) {
                System.out.printf("Mersenne prime Mn for exponent p = %d is %d%n", p, mn);
            }
        }
    }
}

---

Mersenne prime Mn for exponent p = 2 is 3
Mersenne prime Mn for exponent p = 3 is 7
Mersenne prime Mn for exponent p = 5 is 31
Mersenne prime Mn for exponent p = 7 is 127
Mersenne prime Mn for exponent p = 13 is 8191
Mersenne prime Mn for exponent p = 17 is 131071
Mersenne prime Mn for exponent p = 19 is 524287
Mersenne prime Mn for exponent p = 31 is 2147483647
Mersenne prime Mn for exponent p = 61 is 2305843009213693951