埃拉托斯提尼筛与双素测定仪

Question

我制作这个程序是为了找到素数和孪生对。从格式化到内容到技术，我都想要反馈。简而言之:如果它是由一位经验丰富的专业人士撰写的，这又有什么不同呢？

该程序运行五种方法：

• getMax要求输入一个整数，这是查找素数和孪生素数的最大数目。它还具有一个错误消息来捕获不可接受的输入并再次询问。
• 筛子检查0到最大值之间的每一个数字，并返回一个布尔数组，该数组表示每个索引是否为素数。
• primesCount统计了很多素数，并打印出来。
• primesList创建一个包含所有素数的整数数组，并打印它。
• pairsCount计算出有多少对孪生质数，并打印出来。
• pairsList创建一个包含所有孪生素数对的字符串数组，并打印它。

代码：

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    int max = getMax(in);

    boolean[] primesSieve = sieve(max);        
    int primesCount = primesCount(primesSieve);
    int[] primesList = primesList(primesSieve, primesCount);
    int pairsCount = pairsCount(primesList);
    pairsList(primesList, pairsCount);

}   

// User input for maximum number to sieve
public static int getMax(Scanner in) {      
    System.out.print("Maximum number to sieve: ");
    while (!in.hasNextInt()) {
        String input = in.next();
        System.out.println("Error: \"" + input + "\" is not a number. Try again.");
        System.out.print("Maximum number to sieve: ");
    }
    int max = in.nextInt();
    return max;
}

// Create boolean array of prime status of integers less than max
public static boolean[] sieve(int max) {

    // Create initial array and assume all are primes
    boolean[] arePrimes = new boolean[max];
    for (int i = 0; i<max; i++) {
        arePrimes[i] = true;
    }

    // Mark multiples of each prime as non-prime
    for (int i = 2; i<max; i++) {
        if (arePrimes[i]) {
            for (int m = 2; i * m < max; m++) {
                arePrimes[i*m] = false;
            }
        }
    }
    return arePrimes;
}

// Count and print how many primes are less than max    
public static int primesCount(boolean[] primes) {
    int count = 0;
    for (boolean prime : primes) {
        if (prime) {
            count++;
        }
    }
    System.out.println("Number of primes: " + count);
    return count;
}

// Create and print array listing all primes less than max
public static int[] primesList(boolean[] sievedPrimes, int numberOfPrimes) {
    int[] listPrimes = new int[numberOfPrimes-2];
    int n = 0;

    for (int i=2; i<sievedPrimes.length; i++) {
        if (sievedPrimes[i]) {
            listPrimes[n] = i;
            n++;
        }   
    }
    System.out.println("List of primes: " + Arrays.toString(listPrimes));
    return listPrimes;
}

// Count and print the number of twin prime pairs
public static int pairsCount(int[] listOfPrimes) {
    int pairsCount = 0;
    for (int i=0; i<listOfPrimes.length-1; i++) {
        if (listOfPrimes[i+1] - listOfPrimes[i] == 2) {
            pairsCount++;
        }
    }
    System.out.println("Number of twin prime pairs: " + pairsCount);
    return pairsCount;
}

// Create and print array listing all pairs of twin primes less than max
public static String[] pairsList(int[] listOfPrimes, int pairsCount) {
    String[] twinPrimes = new String[pairsCount];
    int n = 0;
    for (int i=0; i<listOfPrimes.length-1; i++) {
        if (listOfPrimes[i+1] - listOfPrimes[i] == 2) {
            twinPrimes[n] = listOfPrimes[i] + " and " + listOfPrimes[i+1];
            n++;
        }
    }
    System.out.println("List of twin prime pairs: " + Arrays.toString(twinPrimes));
    return twinPrimes;
}

Answer 1

有效环

这更像是@Pimgd回答的增编。他建议如下：

//将每个素数的倍数标记为(int i= 2；i*i< max；i++) { if (arePrimes我) { for (int m= i；i*m< max；m++) { arePrimes我*我 = false；}}

如果您查看内部循环，它会执行两次乘法和每次迭代一次添加。您可以删除这样的乘法：

// Mark multiples of each prime as non-prime
for (int i = 2; i * i < max; i++) {
    if (arePrimes[i]) {
        for (int m = i*i; m < max; m += i) {
            arePrimes[m] = false;
        }
    }
}

这只剩下每个循环迭代一个附加项。此外，如果首先将所有偶数标记为非素数，则可以跳过偶数(在每个循环中)，使内循环和外循环都快2x：

// Mark multiples of each prime as non-prime
for (int i = 3; i * i < max; i += 2) {
    if (arePrimes[i]) {
        int increment = i + i;
        for (int m = i*i; m < max; m += increment) {
            arePrimes[m] = false;
        }
    }
}

进一步优化

您可以进行的其他优化如下：

1. 使用每个素数一位而不是一个布尔值来节省空间和改进缓存。
2. 结合筛子使用轮因式分解。