Counting how many different primes are in the factorization of N

Question

I am stuck for a longer time than I'd like to admit in Project Euler Problem 47. I can definitely solve the problem, but my algorithm is too slow. It works when I find the three consecutive numbers with 3 distinct primes. But when you raise that number to 4, I simply cannot find it.

Right now, my function for returning if the value of distinct primes in the factorization of n is:

def count_fact(n):
  counter = 0
  hasFact = False
  num = n
  while num != 1:
    for i in prime_list:
      if num/i*i == num:
        counter += 1
        while num/i*i == num:
          num = num/i
      if counter > TEST_NUM:
        break
  return counter == TEST_NUM

So I was hoping if I could improve that. I was also wondering if there are any other suggestions for me to solve this problem that involves a different approach, to solve it in an appropriate time. My full code is below.

---

import sys

CONST = 40000
TEST_NUM = 4

###GENERATE A LIST OF PRIME NUMBERS###
def isPrime(n):
  isPrime = True
  if n == 2: return True
  elif n==3: return True
  elif n%2 == 0: return False
  elif n%3 == 0: return False
  else:
    i=1
    while 6*i-1 < int(n**0.5)+1:
      if n%(6*i+1) == 0: return False
      if n%(6*i-1) == 0: return False
      i += 1
    return True

def gen_prime(max):
  prime_list = []
  for i in range(2,max+1):
    if isPrime(i):
      prime_list.append(i)
  return prime_list

prime_list = gen_prime(CONST) #global

#######################################

def count_fact(n):
  counter = 0
  hasFact = False
  num = n
  while num != 1:
    for i in prime_list:
      if num/i*i == num:
        counter += 1
        while num/i*i == num:
          num = num/i
      if counter > TEST_NUM:
        break
  return counter == TEST_NUM


def find_consec():
  counter = 0
  isCount = False
  for i in range(2,CONST):
    if count_fact(i):
      if not isCount:
        isCount = True
      counter += 1
    else: 
      if isCount == True:
        isCount = False
      counter = 0
    if counter == TEST_NUM: 
      print [i,i-1,i-2,i-3]
      break



def main():
  find_consec()

if __name__ == '__main__':
  main()

Answer 1

Following python code solves your problem in 1.0240590572357178 secs

from math import sqrt

def PrimeStr(n):
    t=""
    count=0
    while(n%2==0):
        if(count==0):
            t+=str(2)
            t+=" "
            count+=1
        n/=2
    for i in range(3,int(sqrt(n))):
        count1=0
        while(n%i==0):
            if(count1==0):
                t+=str(i)
                count1+=1
                t+=" "
            n/=i
    if n>2:
        t+=str(int(n))
    return t

def finalVerify(a,b,c,d,i):
    lta = [int(s) for s in a.split() if s.isdigit()]
    ltb = [int(s) for s in b.split() if s.isdigit()]
    ltc = [int(s) for s in c.split() if s.isdigit()]
    ltd = [int(s) for s in d.split() if s.isdigit()]

    if(len(lta)==len(ltb)==len(ltc)==len(ltd)==4):
        print("number : "+str(i)+"\n")
        print("lta = "+str(lta))
        print("ltb = "+str(ltb))
        print("ltc = "+str(ltc))
        print("ltd = "+str(ltd))
        lte=[]
        lte +=(lta+ltb+ltc+ltd)
        temp = []
        for item in lte:
            if(len(temp)>=4):
                return 1
            if(item not in temp):
                temp.append(item)
    return 0

for i in range(130000,150000):
    if finalVerify(PrimeStr(i),PrimeStr(i+1),PrimeStr(i+2),PrimeStr(i+3),i):
        print (i,i+1,i+2,i+3)
        raise SystemExit

Answer 2

Your prime number generation is correct. The key part you seem to be missing is an algorithm to factorise a number. Your count_fact function is not good enough, you need some more insight into that.

Once you have that part, the solution to p047 is fairly trivial:

def p047():
    n = 4
    for i in itertools.count():
        if all(len(set(factorise(i + k))) == n for k in range(n)):
            return i

The real work is in writing factorise, a function which returns a list of the prime factors of a number, for example:

>>> factorise(12)
[2, 2, 3]
>>> factorise(4998)
[2, 3, 7, 7, 17]
>>> factorise(4999)
[4999]

It is not hard to implement, just a few lines, but it does require some mathematical insight. There is a very famous algorithm you can use, and I will give you a big hint that you should consider a recursive function here. Runtime of the solution should only be a couple of seconds, so if you're waiting for minutes you are probably heading down the wrong track somewhere.
Good luck!