zhangjinxuan 发表于 2023-1-8 17:29
估计以我的电脑，这道题根本无解
要相信数学，^_^
人造人 发表于 2023-1-8 17:31
要相信数学，^_^
嗯！
tommyyu 发表于 2023-1-8 15:27
正在写
我坚决不会不同意楼主的看法！
使用Python打表的话只需要262144个整数变量即可，但是这些数都会超级大
tommyyu 发表于 2023-1-8 20:20
使用Python打表的话只需要262144个整数变量即可，但是这些数都会超级大
别打表啦{:10_266:}
你说竞赛会不会出现先这种题？
zhangjinxuan 发表于 2023-1-8 21:34
别打表啦
你说竞赛会不会出现先这种题？
不会，顶多用个线性筛
tommyyu 发表于 2023-1-8 21:36
不会，顶多用个线性筛
线性筛也不行啊？
long long 怎么搞？
zhangjinxuan 发表于 2023-1-8 21:37
线性筛也不行啊？
long long 怎么搞？
我感觉质数的判断方法无非就是枚举和筛法，筛法只不过是使用运算进行打表，如果有效率更高的方法也无非是枚举和打表，时间最快的就是提前打好表
高山 发表于 2023-1-8 20:15
我坚决不会不同意楼主的看法！
不会不……少来双重否定……
tommyyu 发表于 2023-1-8 15:27
正在写
感觉我问的问题都不是普及组的朋友能做出来的{:10_266:}
不知道合不合楼主的意思
#include <iostream>
long long a;
int main(){
std::cin >> a;
if (a % 2 == 0 && a % 3 == 0 && a % 5 == 0 && a % 7 == 0) std::cout << "No" << std::endl;
else std::cout << "Yes" << std::endl;
return 0;
}
#include <iostream>
long long a;
int main(){
std::cin >> a;
if (a % 2 == 0 && a % 3 == 0 && a % 5 == 0 && a % 7 == 0) std::cout << "No" << std::endl;
else std::cout << "Yes" << std::endl;
return 0;
}
试试这个行不行
#include <iostream>
using namespace std;
long long a;
int main(){
cin >> a;
if (a % 2 == 0 && a % 3 == 0 && a % 5 == 0 && a % 7 == 0) cout << "No" << endl;
else cout << "Yes" << endl;
return 0;}
本帖最后由 tommyyu 于 2023-1-29 16:04 编辑
我又有了一个好想法{:10_256:}
有诗曰：骗分过样例，打表出省一
既然楼主不让用打表，我们就可以进行骗分{:10_256:}
print(False)时间复杂度仅有O(1)，准确率也高达90%
元豪 发表于 2023-1-15 17:09
试试这个行不行
10000里面有600多个质数
我发现可以通过打表 sqrt(4294967295) 之内的质数来判定{:10_256:}
但是这样不又成打表了么{:10_269:}
所以可以先把 sqrt(4294967295) 里的素数预处理出来{:10_256:}只需要用线性筛就可以了{:10_256:}
感觉这就是这个问题的最优解
jhq999 发表于 2023-1-29 17:47
10000里面有600多个质数
？
tommyyu 发表于 2023-1-29 18:27
我发现可以通过打表 sqrt(4294967295) 之内的质数来判定
但是这样不又成打表了么
所 ...
雀食，但是，42亿，怎么得也得要跑1分钟，我也想过{:10_266:}
不过确实是最优解（我看网上都是一些很奇怪的数学知识，还不一定100%准确）{:10_282:}
zhangjinxuan 发表于 2023-1-29 22:29
雀食，但是，42亿，怎么得也得要跑1分钟，我也想过
不过确实是最优解（我看网上都是一些很奇 ...
sqrt(42亿)，只需要判断 1~65536 以内的质数就可以了
tommyyu 发表于 2023-1-29 22:43
sqrt(42亿)，只需要判断 1~65536 以内的质数就可以了
我感觉好懵逼{:10_291:}
为什么感觉一直在sqrt{:10_277:}(sqrt两遍了