[已解决]能不能在 1 秒, 10兆内存，代码10kb以内100%判断long long范围的数是不是质数？

zhangjinxuan

能的话给出代码

禁止打表！！！

最佳答案

月排行榜 / 总排行榜

tommyyu

2023-1-30 09:59:38

zhangjinxuan 发表于 2023-1-30 09:31
不过我们要的是 long long 范围，1e18, 这个肯定要存下 42亿 之内的质数啊

我觉得就只能依靠数学了

当成 int 了
感觉最快的准确方法还是有 O(sqrt(n)) 的复杂度，所以可能无解
当然，在考试中遇到这种题可以直接骗分
首先判断输入的数是否超过了某个最大值，如果超过了，一律返回不是素数
如果没有超过，就先预处理sqrt(最大值)以内的素数，再进行判断

附赠诗一首：
骗分过样例，暴力出奇迹。暴搜挂着机，打表出省一。N方过百万，暴力踩标算。肥修赛大象，只是代码短。
想要骗到分，一定有方法。图论背模板，数论背公式，动规背方程，高精背代码，要是都不会，干脆输样例。

跳转到最佳答案楼层

zhangjinxuan

tommyyu 发表于 2023-1-8 15:27
正在写

啊，啊，啊？

zhangjinxuan

tommyyu 发表于 2023-1-8 15:27
正在写

long long

zhangjinxuan

人造人 发表于 2023-1-8 17:10
我不打表，我查别人的表，^_^
因为要访问网络，用C++也不是很好整，这里用python了

我真的服了

如果这就是一道编程题，怎么办呢？

zhangjinxuan

人造人 发表于 2023-1-8 17:14
我想这题考的是你的数学知识，我数学不好，^_^

也许是的，我网上搜搜？

zhangjinxuan

KeyError 发表于 2023-1-8 16:55
这里是C/C++交流专区，请不要写Python。

随便吧，毕竟只要不用一些奇奇怪怪的模块，还是可以转换成C++的

zhangjinxuan

人造人 发表于 2023-1-8 17:14
我想这题考的是你的数学知识，我数学不好，^_^

网上的都不100%准确

zhangjinxuan

人造人 发表于 2023-1-8 17:25
这我就没办法了

估计以我的电脑，这道题根本无解

zhangjinxuan

人造人 发表于 2023-1-8 17:31
要相信数学，^_^

嗯！

zhangjinxuan

tommyyu 发表于 2023-1-8 20:20
使用Python打表的话只需要262144个整数变量即可，但是这些数都会超级大

别打表啦

你说竞赛会不会出现先这种题？

zhangjinxuan

tommyyu 发表于 2023-1-8 21:36
不会，顶多用个线性筛

线性筛也不行啊？
long long 怎么搞？

zhangjinxuan

高山 发表于 2023-1-8 20:15
我坚决不会不同意楼主的看法！

不会不……少来双重否定……

zhangjinxuan

tommyyu 发表于 2023-1-8 15:27
正在写

感觉我问的问题都不是普及组的朋友能做出来的

zhangjinxuan

tommyyu 发表于 2023-1-29 18:27
我发现可以通过打表 sqrt(4294967295) 之内的质数来判定
但是这样不又成打表了么
所 ...

雀食，但是，42亿，怎么得也得要跑1分钟，我也想过
不过确实是最优解（我看网上都是一些很奇怪的数学知识，还不一定100%准确）

zhangjinxuan

tommyyu 发表于 2023-1-29 22:43
sqrt(42亿)，只需要判断 1~65536 以内的质数就可以了

我感觉好懵逼

为什么感觉一直在sqrt(sqrt两遍了

zhangjinxuan

jhq999 发表于 2023-1-30 00:40
我的电脑最多大概6到8秒之间，再也想不出来了

这个是100%正确的吗？

zhangjinxuan

tommyyu 发表于 2023-1-30 09:04
因为如果有一个数是42亿以内的合数，则它必定有一个 sqrt(42亿) 以内的质因数。
因此很容易想到两种方法 ...

不过我们要的是 long long 范围，1e18, 这个肯定要存下 42亿 之内的质数啊

我觉得就只能依靠数学了

zhangjinxuan

tommyyu 发表于 2023-1-30 09:59
当成 int 了
感觉最快的准确方法还是有 O(sqrt(n)) 的复杂度，所以可能无解
当 ...

要么数学，要么打表
唉

不过还得看情况，多测题的话先预处理处理划算

zhangjinxuan

jhq999 发表于 2023-1-30 11:04
暴力枚举变形，
质数除了2都是奇数，一个奇数尾数只能是1、3、5、7、9
而尾数是5的奇数一定会被5整除 ...

num = 255
也需许要加一个特判

zhangjinxuan

jhq999 发表于 2023-1-30 11:10
尾数是5，直接判断出来num不是质数
只有出现尾数是1、3、7、9才需要枚举判断是不是质数

这样啊