作者SiriusJinn (假斯汀)
看板C_and_CPP
标题[问题] 判断是否质数演算法会逾时
时间Wed Jul 22 18:05:51 2009
下面是我的程式码，在线上judge时执行时间太久了
有什麽地方可以修改或有更好的演算法可以用吗？
希望大家给个建议！谢谢~
修正过後有点小问题，持续逾时中 = ="
=====================================================
#include <stdio.h>
#include <math.h>
int main(void)
{
int x,y,i,m=0;
while(scanf("%d",&x)!=EOF)
{
y=(int)(sqrt(x));
for(i=2;i<=y;i++)
{
if(x%i==0)
{
m=1;
printf("非质数\n");
break;
}
}
if(m==0)
printf("质数\n");
m=0;
}
return 0;
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.120.90.174
1F：推 VictorTom:1个可以加速的地方是, 回圈跑到根号x就够了:) 07/22 18:09
2F：→ iamivers0n:筛法 07/22 18:23
3F：→ SiriusJinn:那可以直接把for里的x改成pow(x,0.5)吗？ 07/22 18:23
4F：→ SiriusJinn:啊啊~我发现有个地方打错了 = = 07/22 18:26
5F：→ pico2k:m=0可以拿到for回圈之外 07/22 18:30
6F：→ pico2k:开根号求出来的值是double... 07/22 18:31
7F：→ SiriusJinn:嗯呀~这样似乎有问题耶... 07/22 18:35
8F：→ SiriusJinn:我用强制转换看看 07/22 18:40
9F：推 ledia:回圈每次都要算一次 pow 会不会太慢了 可以先算好 又不会变 07/22 18:44
10F：→ ledia:pow 比 sqrt 慢 07/22 18:46
11F：→ SiriusJinn:好的，我用代数取代试试 07/22 18:47
12F：推 legnaleurc:i*i < x 07/22 18:57
13F：→ secondsee:x=sqrt(x); 07/22 19:01
14F：推 yyuto:sqrt复杂度很高 建议使用L大提的i*i<x 07/22 19:12
15F：→ SiriusJinn:若令一个y=(int)(pow(x,0.5))这样y是整数吗？ 07/22 19:12
16F：→ SiriusJinn:用了i*i<x 结果"4"判断为质数耶= = 07/22 19:16
17F：推 Fenikso:i*i <= x 07/22 19:24
18F：推 VictorTom:虽然用i*i<=x比较快, 可是算根号也只需要做一次啊XD 07/22 19:45
19F：→ VictorTom:至於pow/sqrt算出来是double的问题, 直接+0.5取整就好:) 07/22 19:46
20F：推 VictorTom:个人建议, 不需要才这种状况就写下goto.... 07/22 20:50
21F：→ SiriusJinn:我想说能不能加快个执行速度耶... 07/22 21:39
22F：推 liangjr:筛法会快很多 07/23 17:31
24F：推 ledia:筛法会不会比较快也要看查几次~ 07/23 17:49
25F：→ ledia:不过筛法的好处是筛一次出来就可以 binary search (or hash) 07/23 17:49
26F：→ SiriusJinn:我解决了 = = 改用y=(int)(sqrt(x))後不会逾时就过了 07/23 17:58
27F：→ SiriusJinn:然後把start改成break 07/23 17:59
28F：→ SiriusJinn:我补一下我的写法好了 07/23 17:59
※ 编辑: SiriusJinn 来自: 140.120.90.174 (07/23 18:00)
29F：→ SiriusJinn:为了加快速度，for回圈里的东西果然是越少越好 07/23 18:01
30F：推 liangjr:筛法最强的是建一次表之後就可以查表没错 07/23 18:16
31F：→ liangjr:但就算只用一次 筛法还是会比现在的方法快 07/23 18:17
32F：→ liangjr:就算是筛法最基本的 筛掉2的倍数不检查 速度就会快很多了 07/23 18:18
33F：→ liangjr:回圈可以改成 i=3; i<=y; i+=2, x=2的情况另外判断 07/23 18:19