-
Notifications
You must be signed in to change notification settings - Fork 0
/
problem_3.py
35 lines (30 loc) · 812 Bytes
/
problem_3.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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Apr 9 16:27:12 2019
@author: lisestork
"""
#problem 3:
#The prime factors of 13195 are 5, 7, 13 and 29.
#
#What is the largest prime factor of the number 600851475143 ?
import time
def next_prime(n):
for i in range(n+1, 2*n):
if([j for j in range(1,i) if (i % j == 0)] == [1]):
return i
break
def prime_factors(n,primes=[2]):
factors = []
while n != 1:
if(n % primes[-1] == 0):
factors.append(primes[-1])
n = n / primes[-1]
else:
primes.append(next_prime(primes[-1]))
return max(factors)
start = time.time()
x = prime_factors(600851475143)
end = time.time()
print("Script ran for {} seconds".format(end-start))
print("Answer: ", x)