Thread: Feedback: Find even perfect numbers

  1. #1
    Registered User
    Join Date
    May 2017
    Posts
    6

    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;
    }

  2. #2
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    One optimization I've seen is to only check divisors up to the sqrt of the number being checked for primality.

  3. #3
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    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

  4. #4
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help in find perfect numbers
    By san12345 in forum C Programming
    Replies: 6
    Last Post: 12-06-2015, 11:09 AM
  2. Find Perfect Number generator stops at 6
    By JonathanS in forum C Programming
    Replies: 9
    Last Post: 01-17-2012, 07:12 PM
  3. Perfect Numbers
    By iLike in forum C++ Programming
    Replies: 2
    Last Post: 10-18-2009, 12:27 PM
  4. perfect numbers
    By budala in forum C Programming
    Replies: 3
    Last Post: 08-08-2009, 04:16 PM
  5. Perfect Numbers
    By Shadow12345 in forum C++ Programming
    Replies: 13
    Last Post: 09-06-2002, 02:48 PM

Tags for this Thread