我要啦免费统计
求素数时间测试

 

/*
    求素数
    1000W以内的素数，27063ms
    100W以内的素数，1141ms
    10W以内的素数，47ms
  by蔡东赟于无聊的09.09.22日
*/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<assert.h>
#include<ctime>
#include<cmath>
using namespace std;

const int MAX = 10000000;
int findvalue[MAX] = {2};
int find = 1;


bool IsPrim(int value)
{
    assert(value >= 2);

    int flag = (int) sqrt((double)value);

    if(value == 2) 
        return true;

    for (int i = 0; i < find && i <= flag; i++)
    {
        if( (value % findvalue[i]) == 0)
        {
            return false;
        }
    }

    findvalue[find++] = value;
    return true;
}

int main()
{
    double start,finish;
    start = clock();

    for (int j = 3;j < MAX; j++)
    {
        if (IsPrim(j))
        {
            //cout << "" << j << endl;
        }
    }

    finish = clock();

    

    cout << "time:" << (finish - start) << "ms" <<endl;
    system("pause");
    return 0;
}
posted on 2009-09-22 10:38 爬 阅读(1703) 评论(7)  编辑 收藏 引用 所属分类: algorithm

评论:
# re: 求素数时间测试 2009-09-22 11:47 | abettor
将已经求出的素数放入一个数组，判断下一个数是否为素数时，让他去除当前已经得出的所有素数。  回复  更多评论
  
# re: 求素数时间测试 2009-09-22 13:18 | 戴尔电脑
不错啊！！！  回复  更多评论
  
# re: 求素数时间测试 2009-09-22 15:34 | cqh
晕爷还写这个啊，看来是在巩固基础，加油！  回复  更多评论
  
# re: 求素数时间测试[未登录] 2009-09-23 16:30 | vincent
orz..用筛选法吧  回复  更多评论
  
# re: 求素数时间测试 2009-09-23 19:25 | cdy20
@cqh
我在练规范 - - ！！  回复  更多评论
  
# re: 求素数时间测试 2009-09-23 21:43 | cdy20
@vincent
不是  回复  更多评论
  
# re: 求素数时间测试 2009-09-23 21:44 | cdy20
@abettor
是  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 爬