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

人造人

zhangjinxuan 发表于 2023-1-8 17:29
估计以我的电脑，这道题根本无解

要相信数学，^_^

zhangjinxuan

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

嗯！

高山

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

我坚决不会不同意楼主的看法！

tommyyu

使用Python打表的话只需要262144个整数变量即可，但是这些数都会超级大

zhangjinxuan

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

别打表啦

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

tommyyu

zhangjinxuan 发表于 2023-1-8 21:34
别打表啦

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

不会，顶多用个线性筛

zhangjinxuan

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

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

tommyyu

zhangjinxuan 发表于 2023-1-8 21:37
线性筛也不行啊？
long long 怎么搞？

我感觉质数的判断方法无非就是枚举和筛法，筛法只不过是使用运算进行打表，如果有效率更高的方法也无非是枚举和打表，时间最快的就是提前打好表

zhangjinxuan

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

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

zhangjinxuan

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

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

元豪

不知道合不合楼主的意思

1. #include <iostream>
   
2. long long a;
   
3. int main(){
   
4.     std::cin >> a;
   
5.     if (a % 2 == 0 && a % 3 == 0 && a % 5 == 0 && a % 7 == 0) std::cout << "No" << std::endl;
   
6.     else std::cout << "Yes" << std::endl;
   
7.     return 0;
   
8. }

复制代码

元豪

1. #include <iostream>
   
2. long long a;
   
3. int main(){
   
4.     std::cin >> a;
   
5.     if (a % 2 == 0 && a % 3 == 0 && a % 5 == 0 && a % 7 == 0) std::cout << "No" << std::endl;
   
6.     else std::cout << "Yes" << std::endl;
   
7.     return 0;
   
8. }

复制代码

元豪

试试这个行不行

1. #include <iostream>
   
2. using namespace std;
   
3. long long a;
   
4. int main(){
   
5.     cin >> a;
   
6.     if (a % 2 == 0 && a % 3 == 0 && a % 5 == 0 && a % 7 == 0) cout << "No" << endl;
   
7.     else cout << "Yes" << endl;
   
8.     return 0;}

复制代码

tommyyu

我又有了一个好想法
有诗曰：骗分过样例，打表出省一
既然楼主不让用打表，我们就可以进行骗分

1. print(False)

复制代码

时间复杂度仅有O(1)，准确率也高达90%

jhq999

元豪 发表于 2023-1-15 17:09
试试这个行不行

10000里面有600多个质数

tommyyu

我发现可以通过打表 sqrt(4294967295) 之内的质数来判定
但是这样不又成打表了么
所以可以先把 sqrt(4294967295) 里的素数预处理出来只需要用线性筛就可以了
感觉这就是这个问题的最优解

元豪

jhq999 发表于 2023-1-29 17:47
10000里面有600多个质数

？

zhangjinxuan

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

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

tommyyu

zhangjinxuan 发表于 2023-1-29 22:29
雀食，但是，42亿，怎么得也得要跑1分钟，我也想过
不过确实是最优解（我看网上都是一些很奇 ...

sqrt(42亿)，只需要判断 1~65536 以内的质数就可以了

zhangjinxuan

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

我感觉好懵逼

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