CODEWITHSUNDEEP
cprimessieve-of-eratosthenes
vxs8122
vxs8122

Reputation: 844

Command terminated when inputting large number

How come do I get a message "Command terminated" when I try to input a large number (around 10 million)? The program displays whether the number is a prime or not.

See code below:

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

int main ( int argc, char *argv[] )
{
   unsigned long long number;
   bool prime ( unsigned long long );

   printf ("Enter a positive integer greater than 1: ");
   scanf ("%llu", &number );

   prime( number ) ?
      printf ( "%llu is a prime.\n", number ):
      printf ( "%llu is not a prime.\n", number);

   return EXIT_SUCCESS;
}

bool prime ( unsigned long long number )
{
   unsigned long long i, j;
   bool isPrime[number + 1];

   for ( i = 2; i <= number; i++ )
      isPrime[i] = true;

   for ( i = 2; i <= number - 1; i++ )
      for ( j = 1; i*j <= number; j++ )
         isPrime[i*j] = false;

   return isPrime[number];
}

Upvotes: 1

Views: 514

Answers (1)

Floris
Floris

Reputation: 46425

The problem is that you attempt to create an array isPrime on the stack that is larger than the available memory. You should create it on the heap instead, using

bool *isPrime;
isPrime = malloc((number + 1) * sizeof *isPrime);

do this only once obviously, not for every call to the function prime

Notice also that if you just want to know if a number is prime, you only need to search as far as the square root of the number for a factor - and if you find a factor you are done. This makes the size of the array you have to create much more manageable - but it does involve some changes to your algorithm.

afterthought you have a problem in the logic that determines what is a prime number - your inner loop starts with j=1 which means that even prime numbers will be marked as non-prime. The following is "slightly improved" code - although there's more you could do to make it much better:

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

int main ( int argc, char *argv[] )
{
   unsigned long long number;
   bool prime ( unsigned long long );

   printf ("Enter a positive integer greater than 1: ");
   scanf ("%llu", &number );

   prime( number ) ?
      printf ( "%llu is a prime.\n", number ):
      printf ( "%llu is not a prime.\n", number);

   return EXIT_SUCCESS;
}

bool prime ( unsigned long long number )
{
   unsigned long long i, j, sq;
   bool *isPrime;
   sq = ceil(sqrt(number));
   isPrime = malloc((sq + 1)*sizeof *isPrime);

   // generate primes up to the square root of the number
   for ( i = 2; i <= sq; i++ )
      isPrime[i] = true;

   for ( i = 2; i < sq; i++ ) {
      // only need to mark multiples if this is a prime:
      if(isPrime[i]) {
        // start this loop at 2, not 1!
        for ( j = 2; i*j <= sq; j++ ) {
          isPrime[i*j] = false;
        }
      }
    }

   for ( i = 1; i < sq; i++)
   {
    if (isPrime[i] && number%i==0) return false;
   }

   return true;
}

Basic testing:

gcc -Wall generates no errors / warnings

104729 is a prime (it is); code doesn't crash with an input of 10000001 (not a prime).

Upvotes: 3

Related Questions