题目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

1. 5777
   
2. [Finished in 18.9s]
   
3. 
   
4. def isPrime(num):
   
5.         flag = 1
   
6.         for i in range(3,int(num**0.5+1),2):
   
7.                 if num % i == 0:
   
8.                         flag = 0
   
9.         return flag
   
10. 
    
11. hlst = []
    
12. plst = [2,3,5,7,11,13,17,19,23,29,31]
    
13. for num in range(33, 1000000,2):
    
14.         if isPrime(num) == 1:
    
15.                 plst.append(num)
    
16.         else:
    
17.                 hlst.append(num)
    
18.                 for each in plst:
    
19.                         test = ((num - each) * 0.5)**0.5
    
20.                         if test not in range(1000):
    
21.                                 flags = 0
    
22.                         else:
    
23.                                 flags = 1
    
24.                                 break
    
25.                 if flags == 0:
    
26.                         print (num)
    
27.                         exit()

复制代码

飘飞的白杨

1. def isPrime(n):
   
2.     if n <= 1: return False
   
3.     if n == 2: return True
   
4.     if n % 2 == 0: return False
   
5.     for i in range(3,int(n**0.5)+1,2):
   
6.         if n % i == 0: return False
   
7.     return True
   
8. for i in range(3,10000,2):
   
9.     m = 0
   
10.     if not isPrime(i):
    
11.         for j in range(1,int((i//2)**0.5)+1):
    
12.             if isPrime(i - j**2*2):
    
13.                     m = 1
    
14.         if m == 0:
    
15.             print(i)
    
16.             break

复制代码

答案：5777

愤怒的大头菇

1. import math
   
2. def Jh(x):
   
3.     if x>1 and x%2==1:
   
4.         for i in range(3,int(math.sqrt(x)+1),2):
   
5.             if not x%i:
   
6.                 return True
   
7.         return False
   
8. 
   
9. def Prime(x):
   
10.     if x>1:
    
11.         if x==2:
    
12.             return True
    
13.         if x%2==0:
    
14.             return False
    
15.         for i in range(3,int(math.sqrt(x)+1),2):
    
16.             if x%i==0:
    
17.                 return False
    
18.         return True
    
19.     return False
    
20. i = 9
    
21. while True:
    
22.     if Jh(i):
    
23.         tmp = True
    
24.         for j in range(2,i):
    
25.             if Prime(j):
    
26.                 if math.sqrt((i-j)/2)==int(math.sqrt((i-j)/2)):
    
27.                     tmp = False
    
28.                     break
    
29.         if tmp:
    
30.             print(i)
    
31.             break
    
32.     i+=1

复制代码

答案：5777

芒果加黄桃

1. # encoding:utf-8
   
2. # 找出最小的不能写作一个质数与一个平方数的二倍之和的奇合数
   
3. from time import time
   
4. from math import sqrt
   
5. def getPrimes(N):
   
6.     primes = [True] * N
   
7.     primes[0], primes[1] = False, False
   
8.     for i, prime in enumerate(primes):
   
9.         if prime:
   
10.             for j in range(i * i, N, i):
    
11.                 primes[j] = False
    
12.     return [k for k, p in enumerate(primes) if p]
    
13. def euler045(N=10000):
    
14.     s_primes = set(getPrimes(N))
    
15.     l_nums = [t for t in (set([x for x in range(2, N)]) - s_primes) if t % 2]
    
16.     for each in l_nums:
    
17.         flag = False
    
18.         for k in range(1, int(sqrt(each / 2)) + 1):
    
19.             t = each - 2 * k ** 2
    
20.             if t in s_primes:
    
21.                 flag = True
    
22.                 break
    
23.         if not flag:
    
24.             print(each)
    
25.             return
    
26. if __name__ == '__main__':
    
27.     start = time()
    
28.     euler045()
    
29.     print('cost %.6f sec' % (time() - start))
    

复制代码

5777
cost 0.015001 sec

渡风

此代码使用matlab编程
Problem46所用时间为1.052秒
Problem46的答案为5777

1. %% Problem46.m
   
2. %最后编辑时间：2017-06-13 11:00 版本1.0
   
3. %找出第一个奇合数，使得其不能被一个质数和一个数平方的两倍的和表示
   
4. 
   
5. % Problem46所用时间为1.052秒
   
6. % Problem46的答案为5777
   
7. 
   
8. function Output = Problem46()
   
9. tic
   
10. Start = 35;
    
11. Judge = 1;
    
12. while (Judge == 1)
    
13.     Start = Start + 2;
    
14.     Judge =  P64(Start);
    
15. end
    
16. 
    
17. Output = Start;
    
18. toc
    
19. 
    
20. disp('此代码使用matlab编程')
    
21. disp(['Problem46所用时间为',num2str(toc),'秒'])
    
22. disp(['Problem46的答案为',num2str(Output)])
    
23. end
    
24. % 输入一个奇合数，判断其能不能被一个质数和令一个数平方的和；
    
25. function Judge = P64(n)
    
26. if nargin == 0
    
27.     n = 31;
    
28. end
    
29. Judge = 0;
    
30. if isprime(n) == 1
    
31.     Judge = 1;
    
32. else
    
33.     for ii = 3 : 2 : n-2
    
34.         if sqrt((n - ii)/2 ) ==  floor(sqrt((n - ii)/2 ))
    
35.             if  isprime(ii) == 1
    
36.                 Judge = 1;
    
37.                 break
    
38.             end
    
39.         end
    
40.     end
    
41. end
    
42. end

复制代码

najin

用的matlab
结果是：
        5777

时间已过 5.816219 秒。
>>

k往事如烟k

1. def isOddCompNum(num):
   
2.     for i in range(3, int(num**0.5+1)):
   
3.         if num % i == 0:
   
4.             return True
   
5.     else:
   
6.         return False
   
7. 
   
8. def isPrime(num):
   
9.     if num <= 1:
   
10.         return False
    
11.     else:
    
12.         for i in range(2, int(num**0.5+1)):
    
13.             if num % i == 0:
    
14.                 return False
    
15.         else:
    
16.             return True
    
17. 
    
18. def PrimeList(num):
    
19.     PrimeTempList = []
    
20.     for i in range(3, num+1):
    
21.         if isPrime(i):
    
22.             PrimeTempList.append(i)
    
23.     return PrimeTempList
    
24. 
    
25. for i in range(35, 6000, 2):
    
26.     if isOddCompNum(i):
    
27.         PrimeNumTempList = PrimeList(i)
    
28.         for each in PrimeNumTempList:
    
29.             if ((i-each)//2)**0.5 in range(int(((i-each)//2)**0.5+1)):
    
30.                 break
    
31.         else:
    
32.             print(i)
    
33.             break

复制代码

王小召

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

1. import time
   
2. 
   
3. 
   
4. def prime(num_range):
   
5.     bool_num = [1] * (num_range + 1)
   
6.     bool_num[0], bool_num[1] = 0, 0
   
7.     for i, j in enumerate(bool_num):
   
8.         if j:
   
9.             for x in range(i**2, num_range, i):
   
10.                 bool_num[x] = 0
    
11.     return bool_num
    
12. 
    
13. 
    
14. def cal_result():
    
15.     p_list = prime(100000)
    
16.     start = 5
    
17.     while True:
    
18.         if not p_list[start]:
    
19.             mark = 0
    
20.             for z in range(2, start):
    
21.                 if p_list[z] and ((start - z)/2)**0.5 == int(((start - z)/2)**0.5):
    
22.                     mark = 1
    
23.                     break
    
24.             if not mark:
    
25.                 return start
    
26.         start += 2
    
27. 
    
28. print("最小的不能写作一个质数与一个平方数的二倍之和的奇合数是:{}"
    
29.       "\n用时：{} 秒".format(cal_result(), time.process_time()))

复制代码

永恒的蓝色梦想

1. from time import process_time as t
   
2. t1=t()
   
3. def maker(end,choose=True):
   
4.   primelist=[True]*(end+1)
   
5.   primelist[0],primelist[1]=None,False
   
6.   for i,prime in enumerate(primelist[:int(end/2+1)]):
   
7.     if prime:
   
8.       for j in range(2*i,end+1,i):primelist[j]=False
   
9.   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:]
   
10. pl=maker(10000)
    
11. for i in maker(10000,0):
    
12.   flag=True
    
13.   for j in pl:
    
14.     if j>i:break
    
15.     if ((i-j)/2)**0.5%1==0:
    
16.       flag=False
    
17.       break
    
18.   if flag:break
    
19. 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.
对于各个奇合数，枚举平方数，判断奇合数与平方数二倍之差是否为质数即可

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. const int M = 1e6;
   
5. int cnt = 0;
   
6. bool prime[M];
   
7. int factor[M];
   
8. 
   
9. void euler_sieve(){
   
10.   prime[1] = false;
    
11.   for (int i = 2;i <= M;i++) prime[i] = true;
    
12. 
    
13.   for (int i = 2;i <= M;i++){
    
14.     if (prime[i]) factor[++cnt] = i;
    
15.     for (int j = 1;j <= cnt && i*factor[j] < M;j++){
    
16.       prime[i*factor[j]] = false;
    
17.       if (i % factor[j] == 0) break;
    
18.     }
    
19.   }
    
20. }
    
21. 
    
22. bool judge(int x){
    
23.   int t;
    
24. 
    
25.   for (int i = 1;(t = x - 2*i*i) > 1;i++){
    
26.     if (prime[t]) return false;
    
27.   }
    
28. 
    
29.   return true;
    
30. }
    
31. 
    
32. int main(){
    
33.   euler_sieve();
    
34. 
    
35.   for (int i = 35; ;i+=2){
    
36.     if (prime[i]) continue;
    
37.     if (judge(i)) {cout << i << endl; break;}
    
38.   }
    
39. 
    
40.   return 0;
    
41. }
    

复制代码

a1351468657

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int check_prime(int);
   
5. int check_prime(int num)
   
6. {
   
7.         if (num == 2)
   
8.         {
   
9.                 return 1;
   
10.         }
    
11.         if (num == 1)
    
12.         {
    
13.                 return 0;
    
14.         }
    
15.         int i, j;
    
16.         j = sqrt(num);
    
17.         for (i = 2; i <= j; i++)
    
18.         {
    
19.                 if (num % i == 0)
    
20.                 {
    
21.                         return 0;
    
22.                 }
    
23.         }
    
24.         return 1;
    
25. }
    
26. 
    
27. main()
    
28. {
    
29.         int i = 33, j, k, m, n, flag = 1;
    
30. 
    
31.         while (1)
    
32.         {
    
33.                 i += 2;
    
34.                 if (check_prime(i))
    
35.                 {
    
36.                         continue;
    
37.                 }
    
38.                 for (j = i - 2; j > 2; j -= 2)
    
39.                 {
    
40.                         if (check_prime(j))
    
41.                         {
    
42.                                 k = i - j;
    
43.                                 if (k % 2)
    
44.                                 {
    
45.                                         continue;
    
46.                                 }
    
47.                                 else
    
48.                                 {
    
49.                                         k /= 2;
    
50.                                         n = sqrt(k);
    
51.                                         m = n * n;
    
52.                                         if (m == k)
    
53.                                         {
    
54.                                                 flag = 0;
    
55.                                                 break;
    
56.                                         }
    
57.                                 }
    
58.                         }
    
59.                 }
    
60.                 if (flag)
    
61.                 {
    
62.                         printf("%d\n", i);
    
63.                         break;
    
64.                 }
    
65.                 flag = 1;
    
66.         }
    
67.        
    
68. }

复制代码

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

1. import time as t
   
2. import math
   
3. 
   
4. start = t.perf_counter()
   
5. 
   
6. 
   
7. def check_prime(a_num):
   
8.     is_prime = True
   
9.     for i in range(2, int(math.sqrt(a_num) + 1)):
   
10.         if a_num % i == 0:
    
11.             is_prime = False
    
12.     return is_prime
    
13. 
    
14. 
    
15. def is_integer(a_num):
    
16.     delta = 0.00001
    
17.     if abs(a_num - int(a_num)) < delta:
    
18.         return True
    
19. 
    
20. 
    
21. primes = [2, 3]
    
22. odd_num = 3
    
23. while True:
    
24.     odd_num += 2
    
25.     speculation = True
    
26.     if not check_prime(odd_num):
    
27.         speculation = False
    
28.         for prime in primes:
    
29.             if is_integer(math.sqrt((odd_num - prime) / 2)):
    
30.                 speculation = True
    
31.     else:
    
32.         primes.append(odd_num)
    
33.     if not speculation:
    
34.         break
    
35. 
    
36. print(odd_num)
    
37. print("It costs %f s" % (t.perf_counter() - start))
    

复制代码

5777
It costs 0.345528 s