在不使用模數，除法或乘法的情況下查找素數

我的家庭作業任務之一是在數組中查找特定長度內的所有素數。但是，我無法在不使用模數或乘法或除法的情況下嘗試查找素數。任何幫助都非常有必要。我遇到困難的部分被標記爲「測試它是否可以被除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; 
       } 
      }

來源

2016-11-01 solorzke

你爲什麼要避免模/分/乘？這是一個要求嗎？如果是這樣，那麼我懷疑他們希望你實施一個篩號;例如Eratosthenes算法篩 - https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes –

是的！除了加法和減法之外，還需要避免使用算術運算符，部分程序創建Sieve。 – solorzke

如果您需要質數列表，而無需使用模數，除法，乘法還是你必須使用Sieve of Eratosthenes。

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

}

來源

2016-11-02 05:21:18

在不使用模數，除法或乘法的情況下查找素數

回答

相關問題