Problem 47(Distinct primes factors)

Problem 47(Distinct primes factors)

The first two consecutive numbers to have two distinct prime factors are:

\(14 = 2 \times 7\)
\(15 = 3 \times 5\)

The first three consecutive numbers to have three distinct prime factors are:

\(644 = 2^{2} \times 7 \times 23 \)
\(645 = 3 \times 5 \times 43 \)
\(646 = 2 \times 17 \times 19 \).

Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

 

In Python:

import time

def numprimefactor(n):
    i = 2
    count = 0
    while True:
        if n % i == 0:
            count += 1
        while n % i == 0:
            n /= i
            if n == 1:
                return count
        i += 1

startTime = time.time()
i = 2
count = 0
while True:
    if numprimefactor(i) == 4:
        count += 1
        if count == 4:
            break
    else:
        count = 0
    i += 1
print (i - 3)
print(time.time() - startTime, "seconds")

Run time: 282.98886609077454 seconds

 

In Python:

import time
import math

def numprimefactor(n, l):
    count = 0
    for i in l:
        if n % i == 0:
            count += 1
        while n % i == 0:
            n /= i
            if n == 1:
                return count
        i += 1

def seive(n):
    i = 2
    primecodeList =[1 for i in range(1, n + 1)]
    primecodeList[0] = 0
    primeList = []
    while i < n + 1:
        if primecodeList[i - 1] == 1:
            primeList.append(i)
            for j in range(2, n // i + 1):
                primecodeList[i * j - 1] = 0
        i += 1
    return primeList

startTime = time.time()
i = 2
count = 0
primeList = seive(10 ** 3)
while True:
    if numprimefactor(i, primeList) == 4:
        count += 1
        if count == 4:
            break
    else:
        count = 0
    i += 1
print (i - 3)
print(time.time() - startTime, "seconds")

Run time: 3.5005621910095215 seconds

 

Solution: 134043