没有乘法、除法和“for”循环的埃拉托色尼筛法

Question

我和我的朋友正在做一项大学家庭作业练习，目的是在没有任何乘法、除法和 for 循环的情况下制作埃拉托色尼筛。问题是我在我们的教授告诉我们不要使用那些东西之前就写了它，现在我不知道该怎么做。将 for 循环更改为 while 循环没什么大不了的，但我不知道如何去掉代码末尾的最后一个乘法。

我的朋友做了一些我不明白的更改（我会评论他所做的更改），如果有人能向我解释，我将非常感激。总结：

我们需要摆脱 for 循环并用 while 循环替换它们
摆脱代码末尾的乘法，这是我的主要问题。
有助于理解评论中提到的更改。

我们的代码：

import java.util.Scanner;
public class primesieb {

    public static void main(String[] args) {
        //so we declare values and used the scanner to make an input.
        int input = 0;
        Scanner in = new Scanner(System.in);

        System.out.println("give an int bigger that 1:  ");
        input = in.nextInt();

        while (input <= 1)
        {
         //in case the number is smaller than 1.
                System.out.println("the Int must be bigger than 1!.");
                System.out.println("write an Int bigger than 1: ");
                input = in.nextInt(); 
        }
        in.close();
        //now first i wrote it without "+1" but my friend changed it to +1
           boolean[] x = new boolean[input + 1];
        //here I just wanted to add this to set that the position 0 in the string is not a prime number but after thinking I don't see its necessary

               x[0]=false;

        //he did write this commented for loop to assume that all of them are false but for me, it doesn't make sense, pls explain if it's necessary.
        //for (int i = 2; i < x.length; i++) {
          //  x[i] = false;}

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

            while (x[i]) 
            {
                i++;
            }
         // here how can we get rid of the multiplication.
        //the next for loop and if my friend did and a better explain would be nice helping me to represent my code better.
        for (int j = i; j*i < input; j++) 
            {
                x[i * j] = true;
            }
            if (! x[i] && i < input) 
            {
                System.out.println("the number" + i + "is prime. ");
            }
        }
    }       
}

我们在 Eclipse 上测试了这段代码，它可以工作，但我们需要避免使用乘法。

Answer 1

首先，让我们简化您的数字输入：

    Scanner in = new Scanner(System.in);

    int input = 0;

    while (input <= 1) {
        System.out.println("Give an int bigger than 1: ");
        input = in.nextInt();

        if (input <= 1) {
            System.out.println("The int must be bigger than 1!.");
        }
    }

    in.close();

尽量减少 space 的使用，您的朋友不正确：

//now first i wrote it without "+1" but my friend changed it to +1
boolean[] x = new boolean[input + 1];

x[0]=false;

因为你只打印小于 input 的素数（即使 input 是素数）并且你跳过 0 和 1，你可以使 x 三个元素更短：

boolean x[] = new boolean[input - 2];  // all initialized to false

任何 for 循环总是可以展开为 while 循环：

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

在 for 循环设置中的三个分号分隔元素中，第一个出现在 while 循环之前，第二个是 while 循环条件，第三个是while 循环中的最后一条语句：

int i = 2;

while (i < input) {  // 'input' instead of 'x.length' in our new design

    // (the rest of the code that follows below goes here)

    i++;
}

这是一个潜在的问题：

while (x[i]) 
{
    i++;
}

因为在下一个 x[i] 之前没有对 i 进行边界检查。由于在 x 中分配了额外未使用的 space，因此这对您更早起作用。现在我们需要更精确：

while (x[i - 2]) {
    if (++i >= input) {
        break outer;
    }
}

我们正在使用 i - 2，因为我们跳过了缺失的 0 和 1 条目。我们使用 break outer; 而不是 break;，因为我们需要跳出包含此 while 循环的 while 循环。于是回去改：

while (i < input) {

以上改为：

 outer: while (i < input) {

这个 for 循环的转换由于不需要的乘法而有些不同：

for (int j = i; j*i < input; j++) {
    x[i * j] = true;
}

我们将重复添加 i 而不是乘以 i。开始时效率稍低，但其他方面还不错：

int j = i + i;

while (j < input) {
    x[j - 2] = true;
    j += i;
}

不需要这个测试：

if (! x[i] && i < input)

我们已经从上面的工作中知道 x[i] 是 false 和 i < input。所以只需完成：

System.out.println("The number " + i + " is prime.");

i++;  // we added this earlier to finish off our first 'for' to 'while' conversion

如果您仔细遵循这些更改，您现在应该有一个没有 for 循环、没有乘法且没有浪费的数组元素的工作程序。

没有乘法、除法和“for”循环的埃拉托色尼筛法

Eratosthenes sieve without multiply, divide, nor `for` loops

java

primes

sieve-of-eratosthenes