c++ programming 关于prime number的问题(已解决)

小白_86

一个很简单的program:

#include<iostream>
using namespace std;

bool isPrime(int x);

int main()
{

    int num;


cout<<"Please enter an integer number = "<<flush;
cin>>num;


if(isPrime(num)==true)
{
    cout<<num<<" is a prime number ."<<endl;  
}
else
{
    cout<<num<<" is not a prime number ."<<endl;
}





return 0;
}


bool isPrime(int x)
{
    int count,i;
   
count=0;
  
for(i=1;i<=x;i++)      //当'x'是很大的number时, for loop 要浪费很多时间loop 到那个number去。
   {                          //x=1,000,000,000时，出来的result就明显慢了一些。
                              //有什么方法可以减少范围 或 其他可以代替的方法？
     if (x%i==0)
     
         count++;
   }

if (count==2)
    return 1;
else
    return 0;

}

protonwira

多加一个math的header，很多语言都配有数学的library, 物尽其用嘛
具体解决方法去网上找. 总而言之不用这么长的

chrizyuen2

你loop一次就行. 然后把所有答案储存在table内，
以后就直接从table找答案(lookup).
支持到  unit64 还是uint32,就看你requirement了。

ps.Optimization是一门艺术，不是数学。

chrizyuen2

旧没用C++忘记了。
你还能用intel TBB的parallel_for

chrizyuen2

回复 5# centurysage

http://en.wikipedia.org/wiki/Prime_number
中文

小白_86

回复 5# centurysage

这招行不通，当x数值很大的时候就不对了。你的方法会比较直接，可是只能运用在x小于1000

chrizyuen2

回复 9# centurysage

unit64 , 才大约 100个数目，sequential lookup已经很快。 如果不满意，可以用b-tree lookup.

我说的table, 可以是memory table, csv table, xml table, 用sql table 就杀鸡用牛刀了。
memory table 就是array. 任何菜鸟都没有问题