Problem 47

Problem 47

04 July 2003

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

14 = 2 7
15 = 3 5

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

644 = 2² 7 23
645 = 3 5 43
646 = 2 17 19.

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

def isOk47(num):
    count = 0
    for i in primesList:
        if num < i:
            return False
        if num%i == 0:
            count += 1
            if count == 4:
                return True
    return False

def fun47():
    pass
    num = 210#第一个有四个不同的素数因子的数
    while 1:
        if isOk47(num):
            if isOk47(num+1):
                if isOk47(num+2):
                    if isOk47(num+3):
                        return num
                    else:
                        num += 4
                else:
                    num += 3
            else:
                num += 2
        else:
            num += 1

answer is 134043,
time:67.4059998989
用的穷举，不知道有其他好的算法没？
用一个保存计算过的数，可以减少计算时间。
    

def fun47Quick():
    Limit=1000000     # Search under 1 million for now
    factors=[0]*Limit # number of prime factors.
    for i in xrange(2,Limit):
        if factors[i]==0:
            # i is prime
            count =0
            val =i
            while val < Limit:
                factors[val] += 1
                val+=i
        elif factors[i] == 4:
            count +=1
            if count == 4:
                print i-3 # First number
                break
        else:
            count = 0

time:1.82899999619

如果用c语言写的穷举，时间更少
    

#include
#include
 
long p[4800]={2,3};
 
void prime(){
    long a;
    int l=1,i,c;
    for(a=5;;a+=2){
        c=sqrt(a);
        for(i=1;p[i]<=c;i++){
            if(a%p[i]==0)
                c=0;
        }
        if(c){
            p[++l]=a;
            if(a>366)
                break;
        }
    }
}
 
void main(){
    long i,j,l;
    int k,quadruplet=0,count=0;
    prime();
    for(i=210;quadruplet!=4;i++){
        j=sqrt(i);
        l=i;
        for(k=0,count=0;p[k]<=j;k++){
            if(l%p[k]==0){
                while(l%p[k]==0)
                    l/=p[k];
                count++;
            }
        }
        if(l>1)
            count++;
        if(count==4)
            quadruplet++;
        else
            quadruplet=0;
    }
    printf("%li %li %li %li\n",i-4,i-3,i-2,i-1);
}

real    0m0.279s
user    0m0.015s
sys     0m0.031s