blob: fa53dc53b22ccfae6d3a326449e0845e0a4ffef7 (
plain)
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
|
import PIL
import math
import numpy as np
# Problem 3 Largest Prime Factor
###INEFFICIENT METHODS###
# def isPrime(number):
# if (number <=1):
# return False
# for i in range(2,number):
# if(number%i==0):
# return False
# return True
# def prime_factors(number):
#primes = []
# for i in range(number, 2, -1):
# if(number%i==0):
# if (isPrime(i)):
# return i
# return primes
def prime_factors(number):
primes = []
if (number <= 1):
return [1]
a = np.ones(number)
a[0] = 0
a[1] = 0 # not prime
for i in range(2, int(math.ceil(math.sqrt(number)))):
if(a[i] == 1):
j = i**2 # cross out all the multiples
while(j < number):
a[j] = False
j += i
for k in range(2, number):
# is prime is a factor
if(a[k] == 1) and (number % k == 0):
primes.append(k)
return primes
def lpf(number):
factor = 2
while (number > factor):
if(number % factor == 0):
number = number/factor
factor = 2
else:
factor += 1
return factor
out = lpf(600851475143)
print out
|
