Project Euler Problem 179 Solution

Find the number of integers 1  n  10⁷, for which n and n + 1 have the same number of positive divisors. For example, 14 has the positive divisors 1, 2, 7, 14 while 15 has 1, 3, 5, 15.
  



Solution
This problem can be solved using sieve technique.

#include <cstdio>
#include <iostream>
#include <ctime>

using namespace std;

#define sz 10000001
#define hi 3163

long table[sz+1],cnt;

void sieve(){
 int i,j,k;

 for( i = 2; i <= hi; i++){
  if( table[i] == table[i-1])
   cnt++;
  j = i * i;
  table[j]++;
  for( j = j + i; j <= sz; j += i)
   table[j] += 2;
 }
 for( i = hi+1; i <= sz; i++){
  if( table[i] == table[i-1])
   cnt++;
 }
}



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

 st = clock();
 sieve();
 printf("%ld\n",cnt-1);
 en = clock();
 printf("%lf\n",(en-st)/CLOCKS_PER_SEC);

 return 0;
}