[已解决]能不能在 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方过百万，暴力踩标算。肥修赛大象，只是代码短。
想要骗到分，一定有方法。图论背模板，数论背公式，动规背方程，高精背代码，要是都不会，干脆输样例。

跳转到最佳答案楼层

tommyyu

正在写

1. def is_prime(x):
   
2.     if x != 0 and x != 1:
   
3.         for i in range(2, int(x**0.5)+1):
   
4.             if not x%i:
   
5.                 return f'{x}不是质数！'
   
6.     return f'{x}是质数！'
   
7. 
   
8. f = open('prime.cpp', mode='w')
   
9. f.write('''#include <iostream>
   
10. using namespace std;
    
11. int main() {''')
    
12. 53
    
13. f.write('''
    
14.     int n;
    
15.     cin >> n;
    
16.     switch(n) {
    
17. ''')
    
18. for i in range(2147483648):
    
19.     f.write(f'        case {i}:\n')
    
20.     f.write(f'            cout << "' + is_prime(i) + '";\n')
    
21.     f.write(f'            break;\n')
    
22.     if not i % 100000: print(i)
    
23. f.write('''\
    
24.     }
    
25.     return 0;
    
26. }''')
    
27. f.close()
    

复制代码

zhangjinxuan

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

啊，啊，啊？

zhangjinxuan

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

long long

tommyyu

zhangjinxuan 发表于 2023-1-8 15:34
long long

为什么代码要在10k以内啊

tommyyu

zhangjinxuan 发表于 2023-1-8 15:38
每一次的输出至少50字节，输出2147483648是多少字节？

这是多少兆？

我现在的代码应该已经有几千万行了

hveagle

10k=10000啊

tommyyu

有一种更好的打表方法，大概只需要67108864个long long变量就可以打表long long范围的正整数

jhq999

给你们一个样例
9223372036854775783

KeyError

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

这里是C/C++交流专区，请不要写Python。

Mike_python小

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

楼主说不让写了？

C丁洞杀O

额，可以，但是很难，首先如果使用库的话，本身就要加入许多的内存，27kb(<_<)就是一个输出程序就要，2.14 MB，你要自己用汇编写输出输入程序的话可以(<_<)

人造人

我不打表，我查别人的表，^_^
因为要访问网络，用C++也不是很好整，这里用python了

1. sh-5.1$ ls
   
2. main.py
   
3. sh-5.1$ cat main.py
   
4. #!/usr/bin/env python
   
5. #coding=utf-8
   
6. 
   
7. import requests, re
   
8. import time
   
9. 
   
10. def prime(n: int) -> bool:
    
11.     url = r'https://zh.numberempire.com/primenumbers.php'
    
12.     data = {'number': f'{n}'}
    
13.     headers = {'User-Agent': 'Mozilla/5.0 (Windows NT 6.2; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/27.0.1500.56 Safari/537.36'}
    
14.     response = requests.post(url, headers = headers, data = data)
    
15.     pattern = rf'数字.*?{n}.*?不是质数'
    
16.     if re.search(pattern, response.text): return False
    
17.     pattern = rf'数字.*?{n}.*?是质数'
    
18.     if re.search(pattern, response.text): return True
    
19.     raise "未查询到结果"
    
20. 
    
21. time.sleep(0.5)
    
22. print(12, prime(12))
    
23. time.sleep(0.5)
    
24. print(13, prime(13))
    
25. 
    
26. time.sleep(0.5)
    
27. print(0xffffffffffffffff, prime(0xffffffffffffffff))
    
28. time.sleep(0.5)
    
29. print(0x1ffffffffffffff0, prime(0x1ffffffffffffff0))
    
30. sh-5.1$ ./main.py
    
31. 12 False
    
32. 13 True
    
33. 18446744073709551615 False
    
34. 2305843009213693936 False
    
35. sh-5.1$
    

复制代码

zhangjinxuan

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

我真的服了

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

人造人

zhangjinxuan 发表于 2023-1-8 17:12
我真的服了

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

我想这题考的是你的数学知识，我数学不好，^_^

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:24
网上的都不100%准确

这我就没办法了

zhangjinxuan

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

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