本帖最后由 jhq999 于 2023-1-30 08:16 编辑
我的电脑最多大概6到8秒之间，再也想不出来了
#include <stdio.h>
#include <math.h>
int main()
{
long long num=9223372036854775451,s=sqrt(num),i=0,j=0,k=0,flag=1;
//for(flag=0; 0==flag; num-=10,s=sqrt(num))
//根据两个数相乘的积的尾数
//尾数为1：那么i=9,j=11,k=7，9*9=81 1*1=1 3*7=21
//尾数为3:那么i=9,j=11
//尾数为7：那么i=11,j=3
//尾数为1：那么i=11,j=7
for(i=9,j=11,k=7,flag=1; i<s||j<s||k<s; i+=10,j+=10,k+=10)
{
if(0==num%i||0==num%j||0==num%k)
{
flag=0;
break;
}
}
printf("%lld",flag);
return 0;
}
zhangjinxuan 发表于 2023-1-29 22:46
我感觉好懵逼
为什么感觉一直在sqrt(sqrt两遍了
因为如果有一个数是42亿以内的合数，则它必定有一个 sqrt(42亿) 以内的质因数。
因此很容易想到两种方法：
1. 枚举 2 ~ 65536 的整数，看能否整除输入的数
2. 先求出 2 ~ 65536 以内的质数，看能否整除输入进来的数
jhq999 发表于 2023-1-30 00:40
我的电脑最多大概6到8秒之间，再也想不出来了
这个是100%正确的吗？
tommyyu 发表于 2023-1-30 09:04
因为如果有一个数是42亿以内的合数，则它必定有一个 sqrt(42亿) 以内的质因数。
因此很容易想到两种方法 ...
不过我们要的是 long long 范围，1e18, 这个肯定要存下 42亿 之内的质数啊
我觉得就只能依靠数学了
zhangjinxuan 发表于 2023-1-30 09:31
不过我们要的是 long long 范围，1e18, 这个肯定要存下 42亿 之内的质数啊
我觉得就只能依靠数学了
当成 int 了{:10_282:}
感觉最快的准确方法还是有 O(sqrt(n)) 的复杂度，所以可能无解{:10_282:}
当然，在考试中遇到这种题可以直接骗分{:10_256:}
首先判断输入的数是否超过了某个最大值，如果超过了，一律返回不是素数
如果没有超过，就先预处理sqrt(最大值)以内的素数，再进行判断
附赠诗一首：
骗分过样例，暴力出奇迹。暴搜挂着机，打表出省一。N方过百万，暴力踩标算。肥修赛大象，只是代码短。
想要骗到分，一定有方法。图论背模板，数论背公式，动规背方程，高精背代码，要是都不会，干脆输样例。
{:10_256:}
tommyyu 发表于 2023-1-30 09:59
当成 int 了
感觉最快的准确方法还是有 O(sqrt(n)) 的复杂度，所以可能无解
当 ...
要么数学，要么打表{:10_266:}
唉{:10_250:}
不过还得看情况，多测题的话先预处理处理划算
本帖最后由 jhq999 于 2023-1-30 11:06 编辑
zhangjinxuan 发表于 2023-1-30 09:29
这个是100%正确的吗？
暴力枚举变形，
质数除了2都是奇数，一个奇数尾数只能是1、3、5、7、9
而尾数是5的奇数一定会被5整除不是质数
剩下1 、3、 7 、9
而尾数是1的数只能是尾数是1和1、3和7、9和9的乘积，所以选
11、21……——》sqrt(num)
3、13……——》sqrt(num)
9、19……——》sqrt(num)
剩下以此类推
推翻我，举个反例就行
jhq999 发表于 2023-1-30 11:04
暴力枚举变形，
质数除了2都是奇数，一个奇数尾数只能是1、3、5、7、9
而尾数是5的奇数一定会被5整除 ...
num = 255
也需许要加一个特判{:10_282:}
本帖最后由 jhq999 于 2023-1-30 11:13 编辑
zhangjinxuan 发表于 2023-1-30 11:09
num = 255
尾数是5，直接判断出来num不是质数
只有出现尾数是1、3、7、9才需要枚举判断是不是质数
//尾数为1：那么i=9,j=11,k=7，9*9=81 1*1=1 3*7=21
//尾数为3:那么i=9,j=11 7*9=63 1*3=3
//尾数为7：那么i=11,j=3 1*7=7 3*9=27
//尾数为1：那么i=11,j=7 1*9=9 7*7=49
jhq999 发表于 2023-1-30 11:10
尾数是5，直接判断出来num不是质数
只有出现尾数是1、3、7、9才需要枚举判断是不是质数
这样啊
zhangjinxuan 发表于 2023-1-30 11:20
这样啊
在小学竖式计算乘积想到的，
23
x19
------
207
23
-------
437
个位不用和别人加
元豪 发表于 2023-1-15 11:32
不知道合不合楼主的意思
当你学了数学之后，回顾你曾今写的代码，你发现……{:10_256:}
121 是个质数{:10_256:}