Consecutive Positive Divisors

So im trying to solve this problem
Find the number of integers 1 < n < 10^7, 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.

But my code seems to not work or is taking too long. I'm new to programming so please help me

#include<iostream>
#include<cmath>
using namespace std;

int gelli (int x, int y)
{
int b=0;
while (y%x==0)
{
b++;
y = y/x;
}
return b;
}

int posdiv (long long int g)
{
int p=1;

int a=0;
while (g%2==0)
{
a++;
g = g/2;
}
if(a!=0)
p=p*(a+1);


for (int i=3;i<=g;i=i+2)
{
int b=0;
int domingo = gelli (i,g);
if(domingo!=0)
p=p*(domingo+1);
}

if(p==1)
p=p+1;
return p;
}




int main()
{
long long int m,n;
int a,b,c=0;
for(n=2;n<10000000;n++)
{
a = posdiv(n);
m=n+1;
b = posdiv(m);

if(a==b)
c=c+1;
}
cout<<c<<endl;
return 0;
}
Your code seems to work. I tested it with 10000 and got a result of 172. With 100000 I got 1182.
Bigger numbers seem to take ages.
[Would you like to move your post into the "General C++ Programming" Section? It's not specifically a Windows programming exercise.]

Different approach. Might be quicker, but uses a ridiculous amount of memory.
Not sure it is correct - I get different counts to those quoted above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;

const int SIZE = 10000000;

int main()
{
   int i, j, numPairs;

// int count[1+SIZE];                 // may struggle to put large arrays on the stack
   int *count;
   count = new int[1+SIZE];
   for ( i = 1; i <= SIZE; i++ ) count[i] = 0;

   // Accumulate the number of divisors for each integer in count[]
   for ( i = 1; i <= SIZE; i++ )
   {
      j = i;
      while( j <= SIZE )              // this loop accumulates i, 2i, 3i, 4i etc
      {
         count[j]++;
         j += i;
      }
   }

   // Count pairs (optionally outputting them)
   numPairs = 0;
   for ( i = 1, j = 2; i < SIZE; i++, j++ )
   {
      if ( count[i] == count[j] ) 
      {
//       cout << i << " " << j << " " << count[i] << endl;      // uncomment to see pairs of numbers
         numPairs++;
      }
   }

   cout << "Number of pairs = " << numPairs;

   delete [] count;
}
Last edited on
Topic archived. No new replies allowed.