-
Notifications
You must be signed in to change notification settings - Fork 0
/
prob_03.py
65 lines (49 loc) · 1.14 KB
/
prob_03.py
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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Author : Rohit Maurya
"""
# This program takes more time than expected.I Will code sometime later.
from math import sqrt
from timeit import default_timer as timer
start = timer()
def isprime(n):
"""Returns True if n is prime."""
if n == 2:
return True
if n == 3:
return True
if n % 2 == 0:
return False
if n % 3 == 0:
return False
i = 5
w = 2
# Any composite number must have a factor below its square root.
while i * i <= n:
if n % i == 0:
return False
i += w
w = 6 - w
return True
#print(sqrt(600851475143)) Ans: 775146
def prime_list():
"""Create prime number list below 1000000"""
L = []
for n in range(1, 800000):
if isprime(n):
L.append(n)
return L
def main():
primes = prime_list()
n = 600851475143
l = []
for i in primes:
if n%i == 0:
l.append(i)
print(l[-1])
if __name__ == '__main__':
main()
end = timer()
time_taken = (end-start)*1000
print("Time taken to run this program: %d ms"%time_taken)