java - 没有乘法、除法或 `for` 循环的埃拉托斯特尼筛法

Question

我和我的 friend 正在做一项大学作业练习，以制作埃拉托色尼筛，无需任何乘法、除法或 for 循环。 问题是我在教授告诉我们不要使用这些东西之前就写了它，现在我不知道该怎么办。 将 for 循环更改为 while 循环没什么大不了的，但我不知道如何摆脱代码末尾的最后一个乘法。

我的 friend 做了一些我不明白的更改(我将评论他所做的更改)，如果有人可以向我解释它们，我将非常感激。总结一下:

1. 我们需要摆脱 for 循环并用 while 循环替换它们

2. 去掉代码末尾的乘法，这是我的主要问题。

3. 帮助理解评论中指出的更改。

我们的代码:

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();

最大限度地减少空间的使用，您的 friend 的说法不正确:

//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++;
}

因为 i 没有边界检查在下一个之前x[i] 。这之前对您有用，因为 x 中分配了额外的未使用空间。 。现在我们需要更精确:

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 的工作程序。循环，没有乘法，也没有浪费的数组元素。