爲什麼檢查質數在某些非素數上返回true？

我有一個函數檢查數字是否爲素數的問題 - 它返回的是一個數字，當它不是偶數時（甚至有時候數字也是！）。任何想法爲什麼？爲什麼檢查質數在某些非素數上返回true？

int isPrime(long x){ 
    int i; 

    if(x==2||x==3)  return 1; //if i = 2 or 3, return true 
    if(!(x&1))   return 0; //if x is even return false 

    for(i=3;i<=sqrt(x);i+=2) if (x%i == 0) return 0;  //if x is divisible by i return false 

    return 1; 
}

給大家，感謝這麼多的答案，我會+1所有這些，如果我的聲望足夠高：d

可悲的是，我的白癡已經達到了新的高度，我發現了錯誤在我的程序中的其他地方是邏輯的。

來源

2013-04-25 galois

你可以舉一些不返回預期結果的數字嗎？ – JJJ 2013-04-25 06:25:23

你有沒有通過一個負數作爲參數？ – 2013-04-25 06:30:39

它似乎從它返回104760。我正在嘗試第7個項目歐拉問題，找到10001的素數。如果您想查看代碼的其餘部分，請參閱pastebin：http：// pastebin。那些做歐拉問題的人，不要看它！ =））編輯：該代碼需要檢查偶數，順便說一句，因爲它們都是素數。但問題依然存在。 – galois 2013-04-25 06:34:03

可能是因爲sqrt(x)的舍入因此功能調用是浮點數值。所以它可能會小於四捨五入到最接近的整數。

在這種情況下，例如sqrt(25)可以舍入爲4而不是5。

編輯

上104730故障數告訴

if(!(x&1)) return 0; //if x is even return false

似乎並沒有正常工作......所以，你可以嘗試x&1L？

我不知道，但ID的int和long的大小是不同的，（可能）1隱含種姓較短的一種類型，所以可能它會檢查不正確位...

也可以嘗試只是

if(!(x%2)) return 0; //if x is even return false

爲了避免位模式的使用和平臺的依賴。

來源

2013-04-25 06:33:40 Alex

這也是我的想法。我會檢查sqrt（x）+1。 – jbr 2013-04-25 06:34:29

或'ceil（sqrt（x））'。隱含四捨五入是用於分塊。 – Potatoswatter 2013-04-25 06:39:50

我試過檢查sqrt（x）+ 1，它仍然有一些錯誤的回報。 :( – galois 2013-04-25 06:42:21

-1

你沒有檢查是否x是divisble由2

是for循環之前添加return 0如果是2

來源

2013-04-25 06:45:33

這就是這是爲了：如果（！（x＆1））返回0; – galois 2013-04-25 06:51:42

divisble我編輯的for循環到：

for(i=3;i<=x/2;i+=1) if (x%i == 0) return 0;

在我主要通過前100個數字。

int main() 
{ 
    long test=0; 
    int i = 2; 
    for(; i < 100; i++) 
    { 
     test = isPrime(i); 
     if(test == 1) printf("%d ",i); 
    } 

     getchar(); 
     return 0; 
}

這是輸出中：這個北京時間的輸出中的第100個素數：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

我改變了i+=2到i+=1，因爲在代碼中跳過每第二個數字。

來源

2013-04-25 07:06:50 akristmann

使用'sqrt（）'和'i + = 2'是爲了避免額外的不必要的計算。 – Alex 2013-04-25 07:08:26

爲什麼檢查質數在某些非素數上返回true？

回答

相關問題