Java - 素数算法实现不起作用

Question

我写了这段代码,它应该搜索素数并将它们放入数组中.这里是:

int[] prime_array = new int[(int)s.upper_bound];
int index_in_array = 0;
boolean are_we_done = false;
int index = 1;
boolean is_prime = true;

while (!are_we_done) {
    try {
        for (int i = 1; i < index; i++) {
            if ((index%i)==0) {
                is_prime = false;
            }
        }

        if (is_prime) {
            prime_array[index_in_array] = index;
            index_in_array++;
        }

        index++;
        is_prime = true;
    } 
    catch (IndexOutOfBoundsException e) {
        are_we_done = true;
        break;
    }
}

不幸的是,它捕获的唯一主要是1.任何想法为什么它不起作用？

Answer 1

你的for循环正在寻找因素开始i=1,如果index%i==0你认为它不是一个素数.但n%1==0对于所有整数n.

表明某事不是素数的最低因素是2.

编辑:

以下是一些其他建议:

• 使用正确的有界循环来循环您的候选素数.
• 仅检查直至候选素数的平方根的因子.
• 只检查2和奇数作为素数(因为2以上的偶数不是素数,1是单位,不是素数)
• 只检查2和奇数作为因子(因为2以上的偶数不是主要因素)
• 改用筛子.