[已解决]能不能在 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

正在写

def is_prime(x):
    if x != 0 and x != 1:
        for i in range(2, int(x**0.5)+1):
            if not x%i:
                return f'{x}不是质数！'
    return f'{x}是质数！'

f = open('prime.cpp', mode='w')
f.write('''#include <iostream>
using namespace std;
int main() {''')
53
f.write('''
    int n;
    cin >> n;
    switch(n) {
''')
for i in range(2147483648):
    f.write(f'        case {i}:\n')
    f.write(f'            cout << "' + is_prime(i) + '";\n')
    f.write(f'            break;\n')
    if not i % 100000: print(i)
f.write('''\
    }
    return 0;
}''')
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了

sh-5.1$ ls
main.py
sh-5.1$ cat main.py
#!/usr/bin/env python
#coding=utf-8

import requests, re
import time

def prime(n: int) -> bool:
    url = r'https://zh.numberempire.com/primenumbers.php'
    data = {'number': f'{n}'}
    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'}
    response = requests.post(url, headers = headers, data = data)
    pattern = rf'数字.*?{n}.*?不是质数'
    if re.search(pattern, response.text): return False
    pattern = rf'数字.*?{n}.*?是质数'
    if re.search(pattern, response.text): return True
    raise "未查询到结果"

time.sleep(0.5)
print(12, prime(12))
time.sleep(0.5)
print(13, prime(13))

time.sleep(0.5)
print(0xffffffffffffffff, prime(0xffffffffffffffff))
time.sleep(0.5)
print(0x1ffffffffffffff0, prime(0x1ffffffffffffff0))
sh-5.1$ ./main.py
12 False
13 True
18446744073709551615 False
2305843009213693936 False
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
这我就没办法了

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