开启辅助访问勋章商城切换到宽版

o(￣ヘ￣o＃) 任务菌(`へ´*)ノ懒人通道_(:3」∠)_签到领奖官方微博紧急反馈中心

有爱，有技术，有你^_^)y

快捷导航

技术宅社区 | Z站有爱，有技术，有你 ^_^)y»论坛 › 技术区 › 程序设计 › 技术问答 › 【每周一题】素数判定

12 / 2 页下一页

发新帖

查看: 1274|回复: 28

收起左侧

【每周一题】素数判定

签到天数: 17 天

连续签到: 1 天

[LV.4]偶尔看看III

298 主题	139 好友	6万积分

积分: 66622

发表于 2013-4-5 16:37:38 | 显示全部楼层 |阅读模式

╱人◕‿‿◕人╲定下契约

您需要登录才可以下载或查看，没有账号？╱人◕‿‿◕人╲订下契约（注册新用户）

x

我找的都是嗯…比较基础的题嘛，所以各位都快来试一试，这次做对了或者说出自己想法的有奖~！
so，先来上问题：

Problem Description
对于表达式n^2+n+41，当n在（x,y）范围内取整数值时（包括x,y）(-39<=x<y<=50)，判定该表达式的值是否都为素数。

Input
输入数据有多组，每组占一行，由两个整数x，y组成，当x=0,y=0时，表示输入结束，该行不做处理。

Output
对于每个给定范围内的取值，如果表达式的值都为素数，则输出"OK",否则请输出“Sorry”,每组输出占一行。

Sample Input
0 1
0 0

Sample Output
OK

用传统的素数判定一步一步来当然是可以的，但是窝们讲究的是用最小的Code.Len，最短的Exe.Time来解决问题~
@foodszhu @狂奔的瘦子 @兰陵笑忘生 @moxiagy @Mr_Alex @汝欠咱的一生 @terry182 快来讨论讨论方法吧~

稍后会在2楼更新

登录/注册后可看大图

该贴已经同步到 Whisper1166的微博

点评

已经更新到二楼发表于 2013-4-6 19:54

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复

使用道具举报

签到天数: 17 天

连续签到: 1 天

[LV.4]偶尔看看III

298 主题	139 好友	6万积分

积分: 66622

楼主| 发表于 2013-4-5 16:37:50 | 显示全部楼层

本帖最后由 Whisper1166 于 2013-4-6 19:52 编辑

我来发自己的解法吧：
从测试数据看，最大的数的2591，数据量非常小…
所以我的解法就是，打表！
先来看看公式给的都是什么数：
[mw_shl_code=c,true]#include <stdio.h>
int main(void)
{
int i, c;
for (c = 1, i = -39; i <51; i++)
{
printf("%-5d", i * i + i + 41);
if (c++ % 10 == 0) putchar('\n');
}
return 0;
}[/mw_shl_code]

运行结果：
1523 1447 1373 1301 1231 1163 1097 1033 971  911
853 797  743 691 641 593 547 503  461  421
383 347  313 281 251 223 197 173  151  131
113 97    83    71    61    53    47    43    41 41
43    47    53    61    71    83    97 113  131  151
173 197  223 251 281 313 347 383  421  461
503 547  593 641 691 743 797 853  911  971
1033 1097 1163 1231 1301 1373 1447 1523 1601 1681
1763 1847 1933 2021 2111 2203 2297 2393 2491 2591

嗯…然后对刚才的代码稍微做点修改，来输出一个素数判断矩阵：
[mw_shl_code=c,true]#include <stdio.h>
int isprime(int n)
{
int i;

if (n < 2) return 0;
for (i = 2; i * i <= n; i++)
{
if (n % i == 0)
return 0;
}

return 1;
}

int main(void)
{
int i, c;
for (c = 1, i = -39; i <51; i++)
{
printf("%-2d", isprime(i * i + i + 41));
//printf("%-5d", i * i + i + 41);
if (c++ % 10 == 0) putchar('\n');
}
return 0;
}[/mw_shl_code]

运行结果：
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
0 1 1 0 1 1 1 1 0 1

把结果保存到一个数组里，一个判断语句直接提交~

[mw_shl_code=c,true]int main(void)
{
int m, n;
int x[] =
{
      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1
};

while (scanf("%d%d", &m, &n), m || n)
{
      for (m += 39, n += 39; x[m] && m <= n ; m++);
         puts(m > n ? "OK" : "Sorry");
}

return 0;
}[/mw_shl_code]

点评

大神触(￣︶￣)y: 5.0

大神触(￣︶￣)y: 5
我当真以为有公式。。泪目。。。。发表于 2013-4-6 20:07

兰陵笑忘生

粗线学习发表于 2013-4-6 19:57

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

兰陵笑忘生

该用户从未签到

235 主题	249 好友	5万积分

技术宅认证程序员

积分: 52156

发表于 2013-4-5 16:41:05 | 显示全部楼层

昨天还给我妹讲了素数判定→_→

不过是好传统的方法两个for循环

点评

看二楼发表于 2013-4-6 19:53

❤钱伯我的爱！组长一生推❤

回复支持反对

使用道具举报

签到天数: 17 天

连续签到: 1 天

[LV.4]偶尔看看III

298 主题	139 好友	6万积分

积分: 66622

楼主| 发表于 2013-4-5 16:44:36 | 显示全部楼层

兰陵笑忘生发表于 2013-4-5 16:41

登录/注册后可看大图

昨天还给我妹讲了素数判定→_→

不过是好传统的方法两个for循环

俩循环的话时间复杂度就是O(n^2)了吧~

这题可以用0ms的Ext.time通过的哟

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

该用户从未签到

25 主题	59 好友	8779 积分

积分: 8779

发表于 2013-4-5 17:16:41 | 显示全部楼层

用AKS的話應該可以，可是我不會寫AKS.. 只是聽過

点评

其實咱4月10日就要去比賽了，於是很想找些題練下手，這個太好了 :) 发表于 2013-4-5 17:21

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

签到天数: 17 天

连续签到: 1 天

[LV.4]偶尔看看III

298 主题	139 好友	6万积分

积分: 66622

楼主| 发表于 2013-4-5 17:21:40 | 显示全部楼层

terry182 发表于 2013-4-5 17:16

登录/注册后可看大图

用AKS的話應該可以，可是我不會寫AKS.. 只是聽過

AKS应该是O((logn)')吧，这个没有那么复杂的…

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

该用户从未签到

25 主题	59 好友	8779 积分

积分: 8779

发表于 2013-4-5 17:24:22 | 显示全部楼层

Whisper1166 发表于 2013-4-5 17:21

登录/注册后可看大图

AKS应该是O((logn)')吧，这个没有那么复杂的…

質數表，數字這麼小.. 1-100的質數表都夠用了。

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

签到天数: 17 天

连续签到: 1 天

[LV.4]偶尔看看III

298 主题	139 好友	6万积分

积分: 66622

楼主| 发表于 2013-4-5 17:25:35 | 显示全部楼层

terry182 发表于 2013-4-5 17:24

登录/注册后可看大图

質數表，數字這麼小.. 1-100的質數表都夠用了。

嗯嗯……不过1-100应该不够
(-39<=x<y<=50)的话应该要四位数了

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

该用户从未签到

25 主题	59 好友	8779 积分

积分: 8779

发表于 2013-4-5 17:32:37 | 显示全部楼层

Whisper1166 发表于 2013-4-5 17:25

登录/注册后可看大图

嗯嗯……不过1-100应该不够
(-39

sqrt(2591) 大概也就50多，
其實1-49就夠了...

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

签到天数: 17 天

连续签到: 1 天

[LV.4]偶尔看看III

298 主题	139 好友	6万积分

积分: 66622

楼主| 发表于 2013-4-5 17:37:03 | 显示全部楼层

terry182 发表于 2013-4-5 17:32

登录/注册后可看大图

sqrt(2591) 大概也就50多，
其實1-49就夠了...

嗯？…质数表不是都是质数么…
我的意思是测试数据最大的应该就是4位数

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

该用户从未签到

25 主题	59 好友	8779 积分

积分: 8779

发表于 2013-4-5 17:40:48 | 显示全部楼层

Whisper1166 发表于 2013-4-5 17:37

登录/注册后可看大图

嗯？…质数表不是都是质数么…
我的意思是测试数据最大的应该就是4位数 ...

不，因為測試的時候最大的是2591, 然後開方大概是50多..
於是質數表的範圍就是1-49 內的所有質數

评分

参与人数 1	宅币 +15	收起理由
_Nozomi	+ 15	o(￣▽￣)ブ发糖

查看全部评分

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

狂奔的瘦子

签到天数: 1 天

连续签到: 1 天

[LV.1]初来乍到

20 主题	27 好友	1万积分

积分: 11792

发表于 2013-4-5 17:47:29 | 显示全部楼层

我最杵数学题了

点评

魂淡淡o(￣ヘ￣o＃): 5.0

魂淡淡o(￣ヘ￣o＃): 5
同感看见我都绕道走发表于 2013-4-6 10:00

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

签到天数: 17 天

连续签到: 1 天

[LV.4]偶尔看看III

298 主题	139 好友	6万积分

积分: 66622

楼主| 发表于 2013-4-5 17:50:30 | 显示全部楼层

狂奔的瘦子发表于 2013-4-5 17:47

登录/注册后可看大图

我最杵数学题了

计算机科学家以前都是数学家出身的

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

狂奔的瘦子

签到天数: 1 天

连续签到: 1 天

[LV.1]初来乍到

20 主题	27 好友	1万积分

积分: 11792

发表于 2013-4-5 17:53:40 | 显示全部楼层

Whisper1166 发表于 2013-4-5 17:50

登录/注册后可看大图

计算机科学家以前都是数学家出身的

我又不要当科学家

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

签到天数: 17 天

连续签到: 1 天

[LV.4]偶尔看看III

298 主题	139 好友	6万积分

积分: 66622

楼主| 发表于 2013-4-5 17:55:00 | 显示全部楼层

狂奔的瘦子发表于 2013-4-5 17:53

登录/注册后可看大图

我又不要当科学家

所以这和那个屌丝注定孤独一生是一个道理

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

12 / 2 页下一页

发新帖

小黑屋|手机版|技术宅(Z站|基宅) ( 粤ICP备18082987号-1 )

GMT+8, 2025-5-1 23:24 , Processed in 0.103540 second(s), 24 queries , Redis On.

Copyright © 2018 技术宅社区

Powered by Discuz! X3.5

快速回复 返回顶部 返回列表