CODEWITHSUNDEEP
c
Dhaval Mistry
Dhaval Mistry

Reputation: 53

Performance issue in c while dealing with 12 digit number

currently i am working on a program. program is working perfectly but it has performance issue. the code is below.

#include<stdio.h>
int calculate(int temp)
{
    int flag = 0,i = 2,tmp = 0;
    for(i = 2;i < temp;i++)
    {
        if(temp % i == 0)
        {
            return 1;
        }
    }
}
int main()
{
    long int i = 2,j,count = 0,n = 600851475143,flag = 0,prime = 0;
    long int check;
    while(i < n)
    {
        if(n % i == 0)
        {
            check = calculate(i);
            if(check != 1)
            {
                prime = i;
                printf(" Prime  number is : %ld \n", prime);
            }
        }
        i++;
    }
    printf(" Max prime number of %ld is : %ld \n",n,prime);
    return 0;
}

I can't able to get the maximum prime number here. can anyone tell me what should i do it takes too much time what should i do to get output fast?

Upvotes: 0

Views: 79

Answers (1)

StoryTeller - Unslander Monica
StoryTeller - Unslander Monica

Reputation: 170183

  1. If you are looking for a maximum prime, why are you starting at 2? Begin checking at n and work backwards

  2. calculate can run faster since you only need to check for a divisor up to sqrt(temp), if it has a divisor larger than that, it also has a divisor smaller than that.

  3. Your loop increments and decrements can be done in hops of 2. So you'd also halve the range of numbers to check.

  4. Calling printf in the middle of a search loop for when the check fails is just a waste of execution speed. Instead, check for success and break out of the loop.

With these modifications in mind (and your code cleaned from a lot of UB):

#include<stdio.h>
int calculate(long int temp)
{
    long int flag = 0,i = 2,tmp = 0;

    if (temp % 2 == 0)
        return 1;

    for(i = 3; i*i <= temp; i+=2)
    {
        if(temp % i == 0)
        {
            return 1;
        }
    }
    return 0;
}

int main(void)
{
    long int j, count = 0, n = 600851475143, i = n, flag = 0, prime = 0;
    long int check;
    while(i > 0)
    {
        if(n % i == 0)
        {
            check = calculate(i);
            if(check)
            {
                prime = i;
                break;
            }
        }
        i-=2;
    }
    printf(" Max prime number of %ld is : %ld \n",n,prime);
    return 0;
}

Upvotes: 1

Related Questions