Project-Euler/Problem 3.py at master · SuhelMehta9/Project-Euler · GitHub

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
# Problem 3: Largest prime factor
# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?
# For prime numbers upto 1 lakh this program took approximately 20 minutes.
#This program can calculate prime numbers up to 10,000
def prime(num,number):
    dividor = num;
    dividor = dividor-1
    if num<number:
        while(dividor>2):
            if num%dividor==0:

                break;

            value = num%dividor
            if(dividor==3):
                primenum.append(num)

            dividor = dividor-1
    num = num+2


    if num>number:
        return primenum
    prime(num,number)

def more_prime(num,number):
    dividor = num;
    dividor = (dividor-1)/2
    if num<number:
        while(dividor>2):
            if num%dividor==0:

                break;

            value = num%dividor
            if(dividor==3):
                primenum.append(num)

            dividor = dividor-1
    num = num+2


    if num>number:
        return primenum
    prime(num,number)

primenum = [3]
prime(3,5000)
#print(primenum)
number = 5000
while number<10000:
    big_prime = primenum[-1]

    more_prime(big_prime,(big_prime+4999))
    #print(primenum)
    number = number+5000

# To find largest prime factor of number 600851475143
primenum.reverse()
for primeNumber in primenum:
    if 600851475143%primeNumber==0:
        print(primeNumber)
        break;
# This program can be developed, if we can make a list of prime numbers starting with 2 and keep dividing a number with prime number
# to get next prime number.