java - 在不使用模数、除法或乘法的情况下查找质数

Question

我的家庭作业任务之一是找到数组中一定长度内的所有质数。但是，我在不使用模数或乘法或除法的情况下尝试查找素数时遇到了麻烦。任何帮助将非常有义务。我遇到困难的部分标记为“测试它是否可以被 1 和它本身以外的其他数字整除。”

这是我的代码:

class A {
    public static void sieve(int [] array) {

        //List of primes
        int [] primes;
        primes = new int[1000000];

        //Setting the Array
        for(int i = 1; i < array.length; i++) {
            array[i] = i;
        }

        //Finding Primes
        System.out.println("Your primes are: ");
        for(int j = 0; j < array.length; j++) {
            boolean prime = true;
            int num = array[j];

            //Testing if it's divisible by other numbers beside 1 and itself.
            for(int n = 2; n < j; n++) {
                num -= n;
                if(num == 1) {
                    prime = false;
                }
            }

Answer 1

如果您需要素数列表而不使用模数、除法或乘法，则必须使用埃拉托色尼筛法。

const int SIZE=100010;
int status[SIZE]={1};
int sieve(){
    for(int i=0;i<=SIZE;i++)
        status[i]=1;

    for(int i=2;i<=SIZE;i++){
        if(status[i]==1){
            for(int j=2*i;j<=SIZE;j+=i){
                status[j]=0;
            }
        }
    }

}

int main(){
    sieve();
    //check from 2 to 100 which one is prime and which one is not prime
    for(int i=2;i<100;i++){
        if(status[i]==0)
            printf("%d NOT PRIME\n",i);
        else if(status[i]==1)
            printf("%d PRIME\n",i);
    }

}