PROJECT EULER SOLUTION # 47

Solution to problem number 47 of Project Euler.

Question #47

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 prime factors. What is the first of these numbers?

Solution #47

/***********************************************************************************************************/

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include<math.h>

int no_of_distinct_prime_factor(long);

int no_of_distinct_prime_factor(long);

int is_prime(long);

int main()

{

       long c=4,i,tmp,j;

       int flag;

      

       for(i=2;;i++)

       {

              flag=1;

              for(j=0;j<c;j++)

                     if(!(c==no_of_distinct_prime_factor(i+j)))

                     {

                           flag=0;

                           break;

                     }

             

              if(flag)

              {

                     printf("Answer = %d\n",i);

                     break;

              }

       }

      

       printf("Execution time = %f\n",clock()/(float)CLK_TCK);

       system("pause");

}

int no_of_distinct_prime_factor(long n)

{

       int i,counter=0;

       long product=1;

       if(is_prime(n))

              return 1;

       for(i=2;i<=n/2;i++)

       {

              if(product*i > n)

                     break;

              if(n%i==0 && is_prime(i))

              {

                     product*=i;

                     counter++;

              }

       }

       return counter;

}

int is_prime(long n)

{

       int i;

       for(i=2;i<=(long)sqrt((double)n);i++)

              if(n%i==0)

                     return 0;

       return 1;

}

/***********************************************************************************************************/

OUTPUT:-