应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

CyRhmU.jpeg
小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler Project Q7. 欧拉工程第七题
151/2返回列表12下一页
查看: 2526  |  回复: 14
只看楼主@他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 5 个 程序强帖 ，点击这里进行查看

libralibra

至尊木虫 (著名写手)

骠骑将军

[交流] Euler Project Q7. 欧拉工程第七题已有6人参与

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

列出前6个素数:2,3,5,7,11,13,可看出,第6个素数是13.
第10001个素数是多少?
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
1楼2011-05-14 01:12:22
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★
微尘、梦想(金币+2): 用已有函数，也行，不需要干什么都得自己现编，呵呵…… 2011-05-14 19:55:46
matlab code
CODE:
%% find 10001's prime number
function result = euler7()
tic;
x = primes(200000);
result = x(10001);
toc;
end

结果
CODE:
% Elapsed time is 0.008245 seconds.
% ans =
%       104743
赞一下(1人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
2楼2011-05-14 01:13:57
 已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
楼上属于作弊！
回复此楼
3楼2011-05-14 08:42:12
 已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

微尘、梦想

木虫 (知名作家)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3, 程序强帖+1): 谢谢参与交流！ 2011-05-15 19:09:36
来个不作弊的……
CODE:
#include
#include
void main(void)
{
        int n,i=1,j,m,flag;
        for(n=3;1;n+=2)
        {
                flag=0;
                m=sqrt(n);
                for(j=2;j<=m;j++)
                {
                        if(n%j==0)
                                flag++;
                }
                if(flag==0) i++;
                if(i==10001) break;
        }
        printf("%d\n",n);
}

素数的判定方法：用2到sqrt(n)之间的所有整数去除n，如果所有的数都除不尽n，则n为素数，否则n就不是素数。
剩下的一个一个数就行了，一直数到10001……

结果：104743
运行时间：不足1秒

[ Last edited by 微尘、梦想 on 2011-5-14 at 10:36 ]
赞一下(2人) 回复此楼
任风云变幻，我笑对人生！
4楼2011-05-14 10:35:02
 已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
Originally posted by 微尘、梦想 at 2011-05-14 10:35:02:
来个不作弊的……
[code]#include <stdio.h>
#include <math.h>
void main(void)
{
        int n,i=1,j,m,flag;
        for(n=3;1;n+=2)
        {
                flag=0;
                m=sqrt(n);
                for(j=2;j<=m;j++)
                {
                        i ...

这个还可以再优化滴~~~
赞一下(1人) 回复此楼
漩涡的中心有一块空地，空空的。
5楼2011-05-14 10:46:35
 已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+2): 谢谢！ 2011-05-14 19:56:36
余泽成(程序强帖+1): 2011-05-15 19:10:18
虽然使用了筛选法，但这个matlab程序还是需要7秒多。
CODE:
function euler7
    tic;
    n = 10001;
    primes = ones(n,1);
    primes(1:2) = [2 3];
    i = 3;
    m = 5;
    while i <= n
        idx = find(primes > sqrt(m), 1);
        if all(mod(m, primes(1:idx)) ~= 0)
            primes(i) = m;
            i = i + 1;
        end
        m = m + 2;
    end
    disp(num2str(m));
    toc
end
赞一下(3人) 回复此楼
6楼2011-05-14 13:01:05
 已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+2): 很好！ 2011-05-14 19:56:51
余泽成(程序强帖+1): 2011-05-15 19:10:27
Fortran版，感觉很慢，CPU计时，好像只有半秒。
CODE:
Program euler7
    Implicit None
    Integer, Parameter :: N = 10001
    Integer :: Primes(N)
    Integer :: I, M, IDX
    Real    :: StartTime, EndTime

    Call CPU_Time(StartTime)

    Primes(1:2) = (/2,3/)
    I = 3
    M = 5

    Do While(I <= N)
        If(All(Mod(M, Primes(1:I-1)) > 0)) Then
            Primes(I) = M
            I = I + 1
        EndIf
        M = M + 2
    EndDo
    Call CPU_Time(EndTime)
    Print *, M - 2
    Print *, EndTime-StartTime

End Program euler7

[ Last edited by holmescn on 2011-5-14 at 13:58 ]
赞一下(3人) 回复此楼
7楼2011-05-14 13:54:14
 已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+2): 鼓励交流！ 2011-05-14 19:57:06
余泽成(程序强帖+1): 2011-05-15 19:10:42
引用回帖:
Originally posted by holmescn at 2011-05-14 13:01:05:
虽然使用了筛选法，但这个matlab程序还是需要7秒多。

[code]
function euler7
    tic;
    n = 10001;
    primes = ones(n,1);
    primes(1:2) = [2 3];
    i = 3;
    m = 5;
    while i <=  ...

分段筛选试试~
整段筛选的话，每次都需要测试相同的素数，就是说，每次都得从2,3开始测试。就算不需要从2开始测试，3,5,7这样的测试是免不了浪费的。
可以观察函数x*y=z可以发现，以x=y=sqrt(z)为分界线，要么xy，也就是说，如果某数存在因数，肯定是一个在sqrt(z)的左边，另一个在右边。这当然不怎么新鲜，问题在于，既然某个数的一个段落之内可能有好几个因数，那就可以一次性全部找出来而不必下次循环时再来从头开始找。
比如说100，sqrt(100)=10，以10为分界线，如果按照整段筛选的策略，那1~100以内的每个数都需要被遍历，每个数都至少要测试sqrt(n)个素数，排在前面的2,3,5这样的素数大约都需要被重复测试100遍，但是如果以50分段，第一遍，一次性找出前面50个素数，重复测试的次数还是50；第二遍的时候性能开始体现，2只需要测试25遍，3只需要测试16遍，5只需要测试10遍，相比100遍来说，还是好一些。
赞一下(3人) 回复此楼
漩涡的中心有一块空地，空空的。
8楼2011-05-14 14:57:29
 已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+2): 谢谢参与交流！ 2011-05-15 19:10:58
引用回帖:
Originally posted by huycwork at 2011-05-14 14:57:29:
分段筛选试试~
整段筛选的话，每次都需要测试相同的素数，就是说，每次都得从2,3开始测试。就算不需要从2开始测试，3,5,7这样的测试是免不了浪费的。
可以观察函数x*y=z可以发现，以x=y=sqrt(z)为分界线，要 ...

这里的性能损失我想主要是来自一些重复（冗余）计算，比如不用计算每个数的余数，只要有一个能整除，那后面的就不用算了。这一点我不知道matlab是不是给优化掉了。

至于分段，可能是我没有太理解你的意思，每个数在测试是不是质数的时候，都需要用前面N个已经知道的质数去除一下，好像没有什么例外的情况。无论是不是分段。当然，我已经减少了测试的次数，那就是idx那行，只有小于sqrt(m)的质数才会去测试。当然那个find也是一个性能损失。不过，因为我没有做profile，也不改下定论。
赞一下(2人) 回复此楼
9楼2011-05-14 18:03:17
 已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+2, 程序强帖+1): 分析的很详细啊！ 2011-05-15 19:13:06
引用回帖:
Originally posted by holmescn at 2011-05-14 18:03:17:
这里的性能损失我想主要是来自一些重复（冗余）计算，比如不用计算每个数的余数，只要有一个能整除，那后面的就不用算了。这一点我不知道matlab是不是给优化掉了。

至于分段，可能是我没有太理解你的意思， ...

对于整数n而言，减少测试的次数对于整个过程来说非常重要，这个有两个方面，一个是减少测试数据，可以通过sqrt来获得O(lgn)的性能，但是对于每个测试数据而言，前面也还有至多lg(lgn)个数据需要测试，优化测试数据对性能提高是显而易见的。
即使sqrt减少了测试数据，对于相当大的整数而言，比如10^20，sqrt产生的还是10^10个测试数据，即使剔除了偶数，整体规模依然庞大，如果每个数据都去除一遍3,5,7之类的，这些冗余运算自然需要想办法剔除。剔除的最简单办法就是自底向上，把每个非素数全部剔除，像这样：
2，每次递增2，剔除每个偶数，规模减小到1/2
3，每次递增3，剔除每个3的倍数，在2的基础上减少大约1/3
5，每次递增5，剔除每个5的倍数，在3的基础上减少大约1/5
7，每次递增7，剔除每个7的倍数，在5的基础上减少大约1/7
剩下的就全部是素数。这样剔除使数组的规模减少得非常快，而且不断会有新增的素数出现，第一遍需要n/2，第二遍需要大约n/6次，第三遍需要大约n/30次，而所有的测试数据都是素数，理论上说是比那个算法要快，而且没有上面说的冗余，只是实际上实现起来非常困难，需要专门的数据结构支撑，满足两个条件：第一，常数时间的索引元素，第二，常数时间的删除元素。这样的数据结构似乎需要组合链表和数组才能实现。
呃，上面的想法当然有问题，列表不可能是无限长的，所以需要决定一个步长来分段，分段产生的素数用于下一段的计算，但是通常也无法知道下一个素数出现的位置，所以实际上只能估计。由于分段之后的每一个数都是必须要测试的，所以如何分段不是什么性能损失，问题在于每次分段的时候需要初始化段内的数表，这个是个耗时的操作，如何分段取决于问题的实际规模。
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
10楼2011-05-14 19:13:45
 已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 libralibra 的主题更新
151/2返回列表12下一页
普通表情 龙 兔 虎 猫 高级回复(可上传附件)
信息提示
关闭
请填处理意见
关闭