题目46：最小的不能写作一个质数与一个平方数的二倍之和的奇合数是多少？

欧拉计划 · 发表于 2015-5-16 23:28:12

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

Goldbach's other conjecture

It 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:40:23

本帖最后由 jerryxjr1220 于 2016-9-23 14:43 编辑

5777
[Finished in 18.9s]
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 = [2,3,5,7,11,13,17,19,23,29,31]
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()

复制代码

飘飞的白杨 · 发表于 2016-10-29 18:22:00

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

愤怒的大头菇 · 发表于 2016-11-17 22:34:42

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

芒果加黄桃 · 发表于 2017-1-16 11:00:50

# encoding:utf-8
# 找出最小的不能写作一个质数与一个平方数的二倍之和的奇合数
from time import time
from math import sqrt
def getPrimes(N):
primes = [True] * N
primes[0], primes[1] = False, False
for i, prime in enumerate(primes):
if prime:
for j in range(i * i, N, i):
primes[j] = False
return [k for k, p in enumerate(primes) if p]
def euler045(N=10000):
s_primes = set(getPrimes(N))
l_nums = [t for t in (set([x for x in range(2, N)]) - 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:44:24

本帖最后由渡风于 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 ))
if isprime(ii) == 1
Judge = 1;
break
end
end
end
end
end

复制代码

najin · 发表于 2017-9-30 10:58:02

用的matlab
结果是：
5777

时间已过 5.816219 秒。
>>

k往事如烟k · 发表于 2019-3-30 00:27:20

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:00:16

本帖最后由王小召于 2019-6-24 09:02 编辑

最小的不能写作一个质数与一个平方数的二倍之和的奇合数是:5777
用时：0.3276021 秒

import time
def prime(num_range):
bool_num = [1] * (num_range + 1)
bool_num[0], bool_num[1] = 0, 0
for i, j in enumerate(bool_num):
if j:
for x in range(i**2, num_range, i):
bool_num[x] = 0
return bool_num
def cal_result():
p_list = prime(100000)
start = 5
while True:
if not p_list[start]:
mark = 0
for z in range(2, start):
if p_list[z] 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()))

复制代码

永恒的蓝色梦想 · 发表于 2019-8-5 18:59:59

from time import process_time as t
t1=t()
def maker(end,choose=True):
primelist=[True]*(end+1)
primelist[0],primelist[1]=None,False
for i,prime in enumerate(primelist[:int(end/2+1)]):
if prime:
for j in range(2*i,end+1,i):primelist[j]=False
return [i for i,prime in enumerate(primelist) if prime]if choose else [i for i,prime in enumerate(primelist) if not prime and i%2!=0][1:]
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

debuggerzh · 发表于 2020-8-17 10:04:46

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[M];
int factor[M];
void euler_sieve(){
prime[1] = false;
for (int i = 2;i <= M;i++) prime[i] = true;
for (int i = 2;i <= M;i++){
if (prime[i]) factor[++cnt] = i;
for (int j = 1;j <= cnt && i*factor[j] < M;j++){
prime[i*factor[j]] = false;
if (i % factor[j] == 0) break;
}
}
}
bool judge(int x){
int t;
for (int i = 1;(t = x - 2*i*i) > 1;i++){
if (prime[t]) return false;
}
return true;
}
int main(){
euler_sieve();
for (int i = 35; ;i+=2){
if (prime[i]) continue;
if (judge(i)) {cout << i << endl; break;}
}
return 0;
}

复制代码

a1351468657 · 发表于 2021-3-20 21:53:59

#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

ft215378 · 发表于 2021-10-22 15:58:56

#最小的不能写作一个质数与一个平方数的二倍之和的奇合数是多少
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))
#'''

B1tetheDust · 发表于 2022-10-24 22:58:33

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 = [2, 3]
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

账号		自动登录	找回密码
密码			立即注册

题目46：最小的不能写作一个质数与一个平方数的二倍之和的奇合数是多少？

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块