Finding biggest prime number in user-inputted number - C

Question

I have a problem with my code. The topic is to write a C program which finds biggest prime number in the number inputted by user.

Ex.: Enter number: 46656665326

Output: 66566653

This is my code:

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

int is_prime(unsigned long long a)
{
    if(a<=1)
        return 0;
    if(a==2)
        return 1;
    for(unsigned long long p=2; p<a; p++)
        if(a%p==0)
            return 0;
    return 1;
}

unsigned long long find_largest_prime_number(unsigned long long number)
{
    unsigned long long prime=0;
    int count=0;
    unsigned long long count2=1;
    unsigned long long pom=0;
    unsigned long long pom3=0;
    pom3=number;
    while(pom3!=0)
    {
        count++;
        pom3/=10;
    }
    count++;
    int pom_1=0;
    while(pom_1<count)
    {
        count2*=10;
        pom_1++;
    }
    pom=number;
    while(count2>=10)
    {
        unsigned long long pom2=pom;
        while(pom2!=0)
        {
            if(is_prime(pom2))
                if(pom2>prime)
                    prime=pom2;
            pom2/=10;
        }
        count2/=10;
        pom=pom%count2;
    }
    return prime;
}

int main()
{
    unsigned long long x=0;
    printf("Enter number: ");
    int n1=scanf("%llu", &x);
    if(n1!=1)
    {
        printf("incorrect input");
        return 1;
    }
    printf("%llu", find_largest_prime_number(x));
    return 0;
}

The problem is it works with max 13-digit number but it freezes when the input number has more than 13 digits. Ex. it freezes when I enter: 215911504934497

Please help, what's wrong with the code?

Answer 1

The reason for block boils down to this:

int is_prime(unsigned long long a)
{
    ...
    for(unsigned long long p=2; p<a; p++)
        if(a%p==0)
            return 0;
    return 1;
}

If you enter 215911504934497 then the find_largest_prime_number will call is_prime(215911504934497). 215911504934497 is a big number, and doing a%p for each p from 2 to 215911504934497 is cpu expensive (I think at least you could p < a/2). Your program get's stuck in this loop. You can observe that by doing a simple printf inside it:

int is_prime(unsigned long long a)
{
    ...
    for(unsigned long long p=2; p<a; p++) {
        printf("%lld %lld\n", p, a);
        if(a%p==0)
            return 0;
    }
    return 1;
}

Answer 2

Focusing on square root finally solved the issue. is_prime should be looking like that:

int is_prime(unsigned long long a)
{
    int i=0;
    int count=0;
    int test=0;
    int limit=sqrt(a)+1;
    if(a<=1)
        return 0;
    if(a==2)
        return 1;
    if(a%2==0)
        test=1;
    else
        for(i=3; i<limit && !test; i+=2, count++)
            if(a%i==0)
                test=1;
    if(!test)
        return 1;
    else
        return 0;
}

Answer 3

Your code is perfectly correct. It is simply terribly inefficient and therefore takes very, very long time just to find out if a single large number is prime.

Here is better version of is_prime:

• It tests divisors only up to the square root of the number to be tested.
• It only tests odd divisors, if the number is not divisible by two, it's pointless to test if it's divisible by 4, 6, 8 etc.

---

// long long integer square root found somewhere on the internet
unsigned long long isqrt(unsigned long long x)
{
  unsigned long long op, res, one;

  op = x;
  res = 0;

  /* "one" starts at the highest power of four <= than the argument. */
  one = 1LL << 62;  /* second-to-top bit set */
  while (one > op) one >>= 2;

  while (one != 0) {
    if (op >= res + one) {
      op -= res + one;
      res += one << 1;  // <-- faster than 2 * one  
    }
    res >>= 1;
    one >>= 2;
  }
  return res;
}


int is_prime(unsigned long long a)
{
  if (a <= 1 || a == 2 || a % 2 == 0)
    return 0;

  unsigned long long count = 0;
  unsigned long long limit = isqrt(a) + 1;

  for (unsigned long long p = 3; p < limit; p += 2)
  {
    if (a % p == 0)
      return 0;
  }
  return 1;
}

Further optimisations are of course possible. E.g. it is also pointless to test for multiples of 3 if the number was not divisible by 3 etc. Also if you want to find a range of prime numbers there are probably other approaches to be taken into account.

Answer 4

As mentioned by other contributors, and in the comments, your code is "crashing" simply because it is inefficient.

Many of the other contributors have used a more efficient way of checking whether a number is prime by checking that number against its divisors.

HOWEVER, this is not the most efficient manner to go about doing it, especially if you are whether multiple numbers are prime.

In order to make it even faster, I suggest an implementation of the Sieve of Eratosthenes:

#define MAX_N 4294967296 //idk how big of an array your computer can actually handle. I'm using 2^32 here.

//Declare as a global variable for extra memory allocation
//unsigned char is used as it is only 1 byte (smallest possible memory alloc)
//0 for FALSE, 1 for TRUE.
unsigned char is_prime[MAX_N+1];

//Populate the is_prime function up to your input number (or MAX_N, whichever is smaller)
//This is done in O(N) time, where N is your number.
void performSieve(unsigned long long number){
    unsigned long long i,j;
    unsigned long long n = (number>MAX_N)?MAX_N:number; //quick way (ternary operator): "whichever is smaller"

    //Populating array with default as prime
    for(i=2; i<=n; i++) is_prime[i] = 1;

    for(i=4; i<=n; i+=2) is_prime[i] = 0; //all even numbers except 4 is not prime
    for(i=3; i<=n; i+=2){
        if(is_prime[i] == 1)
            for(j=i*i;j<=n;j+=i){ //all the multiples of i except i itself are NOT prime
                is_prime[i] == 0;
            }
    }    
}

//isPrime function
unsigned char isPrime(unsigned long long n){
    if(n<=1) return 0; //edge cases

    //Check if we can find the prime number in our gigantic sieve
    if(n<=MAX_N){
        return is_prime[n]; //this is O(1) time (constant time, VERY FAST!)
    }

    //Otherwise, we now use the standard "check all the divisors" method
    //with all the optimisations as suggested by previous users:
    if(n%2==0) return 0; //even number

    //This is from user @Jabberwocky
    unsigned long long limit = isqrt(a);

    for (unsigned long long p = 3; p <= limit; p += 2) {
        if (a % p == 0) return 0;
    }

    return 1;
}