题目46：最小的不能写作一个质数与一个平方数的二倍之和的奇合数是多少？
Goldbach's other conjectureIt was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
It turns out that the conjecture was false.
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
题目：
Christian Goldbach 提出每个奇合数都可以写作一个质数与一个平方数的二倍之和：
但是这个推测是错误的。
最小的不能写作一个质数与一个平方数的二倍之和的奇合数是多少？
本帖最后由 jerryxjr1220 于 2016-9-23 14:43 编辑
5777
def isPrime(num):
flag = 1
for i in range(3,int(num**0.5+1),2):
if num % i == 0:
flag = 0
return flag
hlst = []
plst =
for num in range(33, 1000000,2):
if isPrime(num) == 1:
plst.append(num)
else:
hlst.append(num)
for each in plst:
test = ((num - each) * 0.5)**0.5
if test not in range(1000):
flags = 0
else:
flags = 1
break
if flags == 0:
print (num)
exit() def isPrime(n):
if n <= 1: return False
if n == 2: return True
if n % 2 == 0: return False
for i in range(3,int(n**0.5)+1,2):
if n % i == 0: return False
return True
for i in range(3,10000,2):
m = 0
if not isPrime(i):
for j in range(1,int((i//2)**0.5)+1):
if isPrime(i - j**2*2):
m = 1
if m == 0:
print(i)
break
答案：5777 import math
def Jh(x):
if x>1 and x%2==1:
for i in range(3,int(math.sqrt(x)+1),2):
if not x%i:
return True
return False
def Prime(x):
if x>1:
if x==2:
return True
if x%2==0:
return False
for i in range(3,int(math.sqrt(x)+1),2):
if x%i==0:
return False
return True
return False
i = 9
while True:
if Jh(i):
tmp = True
for j in range(2,i):
if Prime(j):
if math.sqrt((i-j)/2)==int(math.sqrt((i-j)/2)):
tmp = False
break
if tmp:
print(i)
break
i+=1
答案：5777 # encoding:utf-8
# 找出最小的不能写作一个质数与一个平方数的二倍之和的奇合数
from time import time
from math import sqrt
def getPrimes(N):
primes = * N
primes, primes = False, False
for i, prime in enumerate(primes):
if prime:
for j in range(i * i, N, i):
primes = False
return
def euler045(N=10000):
s_primes = set(getPrimes(N))
l_nums = ) - s_primes) if t % 2]
for each in l_nums:
flag = False
for k in range(1, int(sqrt(each / 2)) + 1):
t = each - 2 * k ** 2
if t in s_primes:
flag = True
break
if not flag:
print(each)
return
if __name__ == '__main__':
start = time()
euler045()
print('cost %.6f sec' % (time() - start))
5777
cost 0.015001 sec 本帖最后由 渡风 于 2017-6-13 12:45 编辑
此代码使用matlab编程
Problem46所用时间为1.052秒
Problem46的答案为5777
%% Problem46.m
%最后编辑时间：2017-06-13 11:00 版本1.0
%找出第一个奇合数，使得其不能被一个质数和一个数平方的两倍的和表示
% Problem46所用时间为1.052秒
% Problem46的答案为5777
function Output = Problem46()
tic
Start = 35;
Judge = 1;
while (Judge == 1)
Start = Start + 2;
Judge =P64(Start);
end
Output = Start;
toc
disp('此代码使用matlab编程')
disp(['Problem46所用时间为',num2str(toc),'秒'])
disp(['Problem46的答案为',num2str(Output)])
end
% 输入一个奇合数，判断其能不能被一个质数和令一个数平方的和；
function Judge = P64(n)
if nargin == 0
n = 31;
end
Judge = 0;
if isprime(n) == 1
Judge = 1;
else
for ii = 3 : 2 : n-2
if sqrt((n - ii)/2 ) ==floor(sqrt((n - ii)/2 ))
ifisprime(ii) == 1
Judge = 1;
break
end
end
end
end
end 用的matlab
结果是：
5777
时间已过 5.816219 秒。
>> def isOddCompNum(num):
for i in range(3, int(num**0.5+1)):
if num % i == 0:
return True
else:
return False
def isPrime(num):
if num <= 1:
return False
else:
for i in range(2, int(num**0.5+1)):
if num % i == 0:
return False
else:
return True
def PrimeList(num):
PrimeTempList = []
for i in range(3, num+1):
if isPrime(i):
PrimeTempList.append(i)
return PrimeTempList
for i in range(35, 6000, 2):
if isOddCompNum(i):
PrimeNumTempList = PrimeList(i)
for each in PrimeNumTempList:
if ((i-each)//2)**0.5 in range(int(((i-each)//2)**0.5+1)):
break
else:
print(i)
break 本帖最后由 王小召 于 2019-6-24 09:02 编辑
最小的不能写作一个质数与一个平方数的二倍之和的奇合数是:5777
用时：0.3276021 秒
import time
def prime(num_range):
bool_num = * (num_range + 1)
bool_num, bool_num = 0, 0
for i, j in enumerate(bool_num):
if j:
for x in range(i**2, num_range, i):
bool_num = 0
return bool_num
def cal_result():
p_list = prime(100000)
start = 5
while True:
if not p_list:
mark = 0
for z in range(2, start):
if p_list and ((start - z)/2)**0.5 == int(((start - z)/2)**0.5):
mark = 1
break
if not mark:
return start
start += 2
print("最小的不能写作一个质数与一个平方数的二倍之和的奇合数是:{}"
"\n用时：{} 秒".format(cal_result(), time.process_time())) from time import process_time as t
t1=t()
def maker(end,choose=True):
primelist=*(end+1)
primelist,primelist=None,False
for i,prime in enumerate(primelist[:int(end/2+1)]):
if prime:
for j in range(2*i,end+1,i):primelist=False
return if choose else
pl=maker(10000)
for i in maker(10000,0):
flag=True
for j in pl:
if j>i:break
if ((i-j)/2)**0.5%1==0:
flag=False
break
if flag:break
print(f'运行结果：{i}\n运行时间：{t()-t1}s')运行结果：5777
运行时间：0.078125s 5777
Process returned 0 (0x0) execution time : 0.043 s
Press any key to continue.
对于各个奇合数，枚举平方数，判断奇合数与平方数二倍之差是否为质数即可
#include<iostream>
using namespace std;
const int M = 1e6;
int cnt = 0;
bool prime;
int factor;
void euler_sieve(){
prime = false;
for (int i = 2;i <= M;i++) prime = true;
for (int i = 2;i <= M;i++){
if (prime) factor[++cnt] = i;
for (int j = 1;j <= cnt && i*factor < M;j++){
prime] = false;
if (i % factor == 0) break;
}
}
}
bool judge(int x){
int t;
for (int i = 1;(t = x - 2*i*i) > 1;i++){
if (prime) return false;
}
return true;
}
int main(){
euler_sieve();
for (int i = 35; ;i+=2){
if (prime) continue;
if (judge(i)) {cout << i << endl; break;}
}
return 0;
}
#include <stdio.h>
#include <math.h>
int check_prime(int);
int check_prime(int num)
{
if (num == 2)
{
return 1;
}
if (num == 1)
{
return 0;
}
int i, j;
j = sqrt(num);
for (i = 2; i <= j; i++)
{
if (num % i == 0)
{
return 0;
}
}
return 1;
}
main()
{
int i = 33, j, k, m, n, flag = 1;
while (1)
{
i += 2;
if (check_prime(i))
{
continue;
}
for (j = i - 2; j > 2; j -= 2)
{
if (check_prime(j))
{
k = i - j;
if (k % 2)
{
continue;
}
else
{
k /= 2;
n = sqrt(k);
m = n * n;
if (m == k)
{
flag = 0;
break;
}
}
}
}
if (flag)
{
printf("%d\n", i);
break;
}
flag = 1;
}
}
5777 #最小的不能写作一个质数与一个平方数的二倍之和的奇合数是多少
from time import *
from math import *
#判断质数
def is_prime(number):
if number > 1:
if number == 2:
return True
if number % 2 == 0:
return False
for a in range(3,int(sqrt(number) + 1),2):
if number % a == 0:
return False
return True
return False
#生成质数列表
def prime(number):
prime = []
for each in range(2, number):
if is_prime(each):
prime.append(each)
return prime
#判断奇数
def is_odd(number):
if number > 1:
if number % 2 != 0:
return True
#判断是否有解
def is_True(number):
for each in prime(number):
n = sqrt((number - each)/2)
if n == int(n):
return True
return False
#奇合数生成器
def get_number(number):
while True:
if is_odd(number) and not is_prime(number):
yield number
number += 1
s = time()
for each in get_number(1):
if not is_True(each):
print(each)
break
e = time()
print("用时%.4f秒" % (e-s))
#'''
import time as t
import math
start = t.perf_counter()
def check_prime(a_num):
is_prime = True
for i in range(2, int(math.sqrt(a_num) + 1)):
if a_num % i == 0:
is_prime = False
return is_prime
def is_integer(a_num):
delta = 0.00001
if abs(a_num - int(a_num)) < delta:
return True
primes =
odd_num = 3
while True:
odd_num += 2
speculation = True
if not check_prime(odd_num):
speculation = False
for prime in primes:
if is_integer(math.sqrt((odd_num - prime) / 2)):
speculation = True
else:
primes.append(odd_num)
if not speculation:
break
print(odd_num)
print("It costs %f s" % (t.perf_counter() - start))
5777
It costs 0.345528 s
页:
[1]