//*******************************
//
// 2014年9月18日星期四，於宿捨撰寫
// 作者：夏華林
//
//********************************
好久沒有沒有更新博客了，最近確實煩心事兒挺多，已經大三了，真的靜下心來好好看看書了。
今天要說的，就是一個由IsPrime算法引發的細節問題，我這裡說的細節，是我所認為的，若有不妥，望指正！
一個簡單的IsPrime算法的實現如下：
1 bool IsPrime(int n)
2 {
3 int i;
4
5 if(n % 2 == 0)return false;
6 for(i = 3; i <= sqrt(n); i += 2)
7 {
8 if(n%i == 0)return false;
9 }
10 return true;
11 }
這段代碼中有一些嚴重的錯誤，很明顯的就是，當參數為1和2的時候，函數就會返回一個錯誤的答案，要解決這個問題，最簡單的方法就是單獨檢查1和2，可以在函數的開頭簡單的加入：
if(n <= 1)return false; if(n == 2)return true;
還有一個性能上的問題，IsPrime算法的本意是為了提高效率，但實際情況下，有時候卻會比老的算法花的時間更長。
這種問題存在於for循環的控制行中：
for(i = 3; i <= sqrt(n); i += 2)
盡管現代計算機能在相當短的時間內計算平方根，但，計算平方根還是會比執行簡單的算術運算要花的時間要長。程序中，每執行一次循環，都要計算一下sqrt(n)，而n在整個循環中都是不變的量，那麼我們每次循環都計算一下sqrt(n)就顯得不那麼劃算，為了避免一次次的調用sqrt()函數，可以在循環前先計算出sqrt(n)，把它存入一個變量，例如:
double limit = sqrt(n); for(i = 3; i <= limit; i += 2)
這個簡單的改變，將明顯的改善了IsPrime算法的實現效率。
這個IsPrime算法還有一個很難查出的問題，發現這個邏輯錯誤是很難的，因為它可能在你成千上萬的測試例子中都不會出現，而對於一些特殊的測試例子，這個實現可能會在一些機器上能得出正確結果，而在另一個機器上得出不正確的答案。
為了理解這個問題，我覺得自己還是有必要再補寫一篇關於計算機浮點數相關的文章，但限於篇幅，這裡就不詳細敘述其原理了
對浮點數判斷嚴格的相等，是一個危險的行為。假設n是49，它是7的平方，當計算機對49調用sqrt()函數時，會返回什麼？在嚴格的數學領域，這個平方根是7，但計算機並不是在這個領域內運作的，它返回的僅僅是一個接近7的浮點數，而這個數可能是6.9999999999999999999，盡管這個數很接近7，但這個差別足以影響i<=limit的結果。如果i是7，而limit是6.999999999，則循環的最後一個周期將不會得到執行，程序永遠不會檢查到是否可以整除7，而7又是49唯一的質因子，這樣程序會錯誤的將49分類素數。另一方面，如果sqrt(49)返回的是7.0或者7.0000000001，那麼IsPrime算法將會得到正確的答案。因而，這個實現的正確性居然要取決於硬件是如何執行浮點數運算的，而讓一個算法的正確性依賴於運行它的計算機的特性是一個嚴重的錯誤。這個問題很容易解決，如果n的平方根小於某一個界限，為了保險起見，我們總傾向於多檢查一個可能的約數，多測試一個約數並不會有什麼害處，僅僅是付出一個非常小的代價，就能確保算法能在不同硬件上得到正確性的執行，這樣的取捨對於我們來說是相當合算的
只要簡單的修改：
double limit = sqrt(n) + 1;
IsPrime算法本身是一個非常簡單的，但其中的細節卻值得我們引起足夠的重視。
首先我假設閣下是要算法,不是要實現,希望沒有理解錯,否則要白忙活半天
設計一個函數IsPrime判斷輸入是否為素數,輸入一個正整數,如果是返回該數(真),若否,則返回0(假),調用是不判斷返回直接加入也不會增加總和的值
循環調用IsPrime相加,不需判斷
IsPrime,首先判斷輸入是否為偶數,若是則返回0,退出
若否,則尋找其可整除的數,該數必須滿足以下條件,①奇數(步長為2)②介於2到輸入的平方根之間的正整數,若能找到,返回0,否則反之
這只是基於一般的考慮,針對這個問題,可以從外部控制,首先初始化和為2,從3開始作為IsPrime的輸入調用IsPrime,並設置步長為2,可避免輸入偶數,這樣就可以去掉IsPrime內部相應的分支,外部也沒有增加分支,可針對問題加速計算
愚見,僅供參考,
順便問一聲,高一就研究算法嗎?好好學習!
#include <stdio.h>
#include <math.h>
int isprime(int n)
{
int k=(int)sqrt(n);
for(int i=2;i<=k;i++)
{
if(n%i==0)
return 0;
}
return 1;
}
void main()
{
int a;
scanf("%d",&a);
if(isprime(a))
printf("%d is a prime.\n",a);
else
printf("%d is not a prime.\n",a);
}
