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

欧拉计划

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

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()

飘飞的白杨

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 = [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

渡风

此代码使用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

用的matlab
结果是：
        5777

时间已过 5.816219 秒。
>>

k往事如烟k

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

王小召

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

永恒的蓝色梦想

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

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

#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

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

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