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

jhq999

我的电脑最多大概6到8秒之间，再也想不出来了

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int main()
   
5. {
   
6.     long long num=9223372036854775451,s=sqrt(num),i=0,j=0,k=0,flag=1;
   
7. 
   
8.     //for(flag=0; 0==flag; num-=10,s=sqrt(num))
   
9.     //根据两个数相乘的积的尾数
   
10.     //尾数为1：那么i=9,j=11,k=7，9*9=81 1*1=1 3*7=21
    
11.     //尾数为3:那么i=9,j=11
    
12.     //尾数为7：那么i=11,j=3
    
13.     //尾数为1：那么i=11,j=7
    
14.         for(i=9,j=11,k=7,flag=1; i<s||j<s||k<s; i+=10,j+=10,k+=10)
    
15.         {
    
16.             if(0==num%i||0==num%j||0==num%k)
    
17.             {
    
18.                 flag=0;
    
19.                 break;
    
20.             }
    
21.         }
    
22. 
    
23.     printf("%lld",flag);
    
24.     return 0;
    
25. 
    
26. }

复制代码

tommyyu

zhangjinxuan 发表于 2023-1-29 22:46
我感觉好懵逼

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

因为如果有一个数是42亿以内的合数，则它必定有一个 sqrt(42亿) 以内的质因数。
因此很容易想到两种方法：
1. 枚举 2 ~ 65536 的整数，看能否整除输入的数
2. 先求出 2 ~ 65536 以内的质数，看能否整除输入进来的数

zhangjinxuan

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

这个是100%正确的吗？

zhangjinxuan

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

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

我觉得就只能依靠数学了

tommyyu

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

我觉得就只能依靠数学了

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

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

zhangjinxuan

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

要么数学，要么打表
唉

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

jhq999

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)
剩下以此类推

推翻我，举个反例就行

zhangjinxuan

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

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

jhq999

zhangjinxuan 发表于 2023-1-30 11:09
num = 255

尾数是5，直接判断出来num不是质数
只有出现尾数是1、3、7、9才需要枚举判断是不是质数

jhq999

//尾数为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

zhangjinxuan

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

这样啊

jhq999

zhangjinxuan 发表于 2023-1-30 11:20
这样啊

在小学竖式计算乘积想到的，
23
x19
------
207
23
-------
437
个位不用和别人加

zhangjinxuan

元豪 发表于 2023-1-15 11:32
不知道合不合楼主的意思

当你学了数学之后，回顾你曾今写的代码，你发现……

121 是个质数