Thread: Feedback: Find even perfect numbers

Hey,

I wrote a program by the help of Perfect number - Wikipedia to find all even perfect numbers up to 10000. What can I improve? Did I make any performance errors?

Code:

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool PrimeCheck(int number);

int main(void)
{
  int number;
  int p = 2;
  bool stop = true;

  do
  {
    if (PrimeCheck(pow(2, p) - 1))
    {
      number = pow(2, p - 1)*(pow(2, p) - 1);
      
      if (number <= 10000)
      {
        printf("%d\n", number);
      }
    }

    if (number >= 10000)
    {
      stop = false;
    }

    p++;
  } while (stop);

  return 0;
}

bool PrimeCheck(int number)
{
  int i;

  for (i=2; i<number; i++)
  {
    if (number%i == 0)
    {
      return false;
    }
  }
  return true;
}

One optimization I've seen is to only check divisors up to the sqrt of the number being checked for primality.

There's some math explanation here if you like it. I'd say reducing you're loop from O(N) to O(log_2 N) is quite an improvement!

algorithm - Why do we check up to the square root of a prime number to determine if it is prime? - Stack Overflow

To test if a number is prime you only need to check divisors up to (and including) the square root of the number. And you can test for divisibility by 2 separately and then test only odd divisors.

And you don't need to use the pow function.

You really need to be careful about numeric overflow with this algorithm.

Code:

#include <stdio.h>
#include <stdbool.h>
#include <inttypes.h>

typedef int64_t INT;
#define FORMAT PRId64

#define HIGH_N 10000000000

bool isprime(INT n);

int main(void) {
  INT n, power = 4;
 
  for (;;) {
    if (isprime(power - 1)) {
      n = power / 2 * (power - 1);
      if (n > 10000000000)
        break;
      else
        printf("%" FORMAT "\n", n);
    }
    power *= 2;
  }
 
  return 0;
}
 
bool isprime(INT n) {
  if (n % 2 == 0)
      return n == 2;
  for (INT i = 3; i * i <= n; i += 2)
    if (n % i == 0)
      return false;
  return true;
}