Project Euler Problem 47 Solution

Problem Statement :

     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?

Approach 1 :

    It can be solved by brute force easily. First for we have to generate prime factors for integer greater than 10 to 1000,000 using trial division. And at the same time we have check the given property.

Here is the C++ implementation of the idea.

#include <vector>
#include <algorithm>
#include <list>
#include <iostream>

using namespace std;

void fac(vector &v,long N){
 long tmp,j;
 bool f;

 for(j=2;j*j1)
  v.push_back(N);
}

int main(){
 long i,j,k,l,temp,tmp;

 vectorv,v2,v3,v4,ans;
 vector::iterator it;
 bool f;

 for(i=100000;i<600000;){
  v.clear(); 
  fac(v,i);
  i++;
  if(v.size() >= 4){
   v2.clear(); 
   fac(v2,i);
   i++;
  }
  else
   continue;
  
  if(v2.size() >= 4){
   v3.clear(); 
   fac(v3,i);
   i++;
  }
  else continue;

  
  if(v3.size() >= 4){
   v4.clear(); 
   fac(v4,i);
   i++;
  }
  else continue;

  
  if(v4.size() >= 4){
   for(it = v.begin(); it != v.end();it++){
    ans.push_back(*it);
   }
   for(it = v2.begin(); it != v2.end();it++){
    ans.push_back(*it);
   }
   for(it = v3.begin(); it != v3.end();it++){
    ans.push_back(*it);
   }
   for(it = v4.begin(); it != v4.end();it++){
    ans.push_back(*it);
   }
   sort(ans.begin(), ans.end());

   bool con = true;

   for(it = ans.begin()+1;it != ans.end();it++){
    if(*it == *(it-1)){
     con = false;
     break;
    }
   }

   if(con){
    cout << i-4 << '\n';
    break;
   }
  }
 }

 return 0;
}

Output :

Approach 2:
     We can generate primes using sieve and at the same time we can count number of prime factors of a number. Next time when we will get 4 consecutive number having prime factors greater than 4 we will factorized these numbers using trial division and also check if the prime factors of these number are distinct.

Here is the C++ of this idea.

#include <vector>
#include <algorithm>
#include <set>
#include <iostream>
#include <cstdio>

using namespace std;
#define sz 1000001
#define max 1001

long f[sz];
bool p[sz];
long primeTable[78500],ind=0;

void sieve(){
 long i,j,k,l,temp,tmp;

 p[0] = p[1] = true;
 primeTable[ind++] = 2;
 f[2]++;
 for(i = 4; i < sz; i += 2){
  p[i] = true;
  f[i]++;
 }

 for(i = 3;i < max;i += 2){
  if(!p[i]){
   primeTable[ind++] = i;
   f[i]++;
   for(j = i+i;j < sz;j += i){
    p[j] = true;
    f[j]++;
   }
  }
 }
 for(i = max+2;i < sz;i += 2){
  if(!p[i]){
   f[i]++;
   primeTable[ind++] = i;
  }
 }
}

bool calc(long n){
 long i,j,k,l,tmp;
 sets;

 for(j = 0; j < 4; j++){//factoring four consecutive numbers
  i = n + j;
  l = 0;
  while(primeTable[l]*primeTable[l] <= i && l < ind){
   tmp = 1;
   while(i % primeTable[l] == 0){
    i /= primeTable[l];
    tmp *= primeTable[l];
   }
   if(tmp != 1)
    s.insert(tmp);
   l++;
  }
  if( i > 1)
   s.insert(i);
 }
 return s.size() >= 16;//checking if they are distinct
}

int main(){
 long i,j,k,l;

 setans;
 sieve();

 for(i=100000;i<600000;){
  if(f[i++] < 4)
   continue;
  if(f[i++] < 4)
   continue;
  if(f[i++] < 4)
   continue;
  if(f[i++] < 4)
   continue;
  if(calc(i-4)){
   printf("%ld\n",i-4);
   break;
  }
 }

 return 0;
}

Output: