TheAlgorithms_Python/project_euler/problem_046/sol1.py at problem_122 · mindaugl/TheAlgorithms_Python · GitHub

Name: TheAlgorithms_Python/project_euler/problem_046/sol1.py at problem_122 · mindaugl/TheAlgorithms_Python · GitHub
Rating: 4.5 (6035 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
"""
Problem 46: https://projecteuler.net/problem=46

It was proposed by Christian Goldbach that every odd composite number can be
written as the sum of a prime and twice a square.

9 = 7 + 2 x 12
15 = 7 + 2 x 22
21 = 3 + 2 x 32
25 = 7 + 2 x 32
27 = 19 + 2 x 22
33 = 31 + 2 x 12

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?
"""

from __future__ importannotations

importmath


defis_prime(number: int) ->bool:
"""Checks to see if a number is a prime in O(sqrt(n)).

 A number is prime if it has exactly two factors: 1 and itself.

 >>> is_prime(0)
 False
 >>> is_prime(1)
 False
 >>> is_prime(2)
 True
 >>> is_prime(3)
 True
 >>> is_prime(27)
 False
 >>> is_prime(87)
 False
 >>> is_prime(563)
 True
 >>> is_prime(2999)
 True
 >>> is_prime(67483)
 False
 """

if1<number<4:
# 2 and 3 are primes
returnTrue
elifnumber<2ornumber%2==0ornumber%3==0:
# Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
returnFalse

# All primes number are in format of 6k +/- 1
foriinrange(5, int(math.sqrt(number) +1), 6):
ifnumber%i==0ornumber% (i+2) ==0:
returnFalse
returnTrue


odd_composites= [numfornuminrange(3, 100001, 2) ifnotis_prime(num)]


defcompute_nums(n: int) ->list[int]:
"""
 Returns a list of first n odd composite numbers which do
 not follow the conjecture.
 >>> compute_nums(1)
 [5777]
 >>> compute_nums(2)
 [5777, 5993]
 >>> compute_nums(0)
 Traceback (most recent call last):
 ...
 ValueError: n must be >= 0
 >>> compute_nums("a")
 Traceback (most recent call last):
 ...
 ValueError: n must be an integer
 >>> compute_nums(1.1)
 Traceback (most recent call last):
 ...
 ValueError: n must be an integer

 """
ifnotisinstance(n, int):
raiseValueError("n must be an integer")
ifn<=0:
raiseValueError("n must be >= 0")

list_nums= []
fornuminrange(len(odd_composites)):
i=0
while2*i*i<=odd_composites[num]:
rem=odd_composites[num] -2*i*i
ifis_prime(rem):
break
i+=1
else:
list_nums.append(odd_composites[num])
iflen(list_nums) ==n:
returnlist_nums

return []


defsolution() ->int:
"""Return the solution to the problem"""
returncompute_nums(1)[0]


if__name__=="__main__":
print(f"{solution() =}")