CODEWITHSUNDEEP
cprimes
Luka
Luka

Reputation: 207

Can I make this C program any faster?

I need to make a program which prints all the prime numbers, here is that I have done:

#include <stdio.h>

int main(void) {
    long long t,m,n,i,i2,i3,found;
    float p;
    scanf ("%lld" , &t);
    for (i=1;i<=t;i++) {
        scanf ("%lld%lld" , &m ,&n);
        for (i2=m;i2<=n;i2++) {
            found=0;
            for (i3=2;i3<=i2/2;i3++) {
                p=(float)i2/i3;
                p=p-i2/i3;
                if (p==0) {
                    found=1; 
                }
            }
            if ((found==0) && (i2!=1)) {
                printf ("%lld\n" , i2); 
            }
        }
        printf ("\n");
    }
    return 0;
}

my time limit is 6 seconds, and with this code it's impossible, also the difference between m and n is 100000 maximum, and 1<=n<=m<=1000000000

Upvotes: 0

Views: 149

Answers (2)

haccks
haccks

Reputation: 106002

For this problem the constraints (ranges) are very large so better to use Miller–Rabin primality test method.

I changed my mind. You can use Sieve of Eratosthenes algorithm.

Here are the steps to find all prime numbers less than or equal to a given integer n by Sieve of Eratosthenes method:

  • First create an array of consecutive integers from 2 to n: (2, 3, 4, ..., n).
  • let p be an integer variable, initialize it with 2, the first prime number.
  • Starting from p, count up in increments of p and cross out all the multiples of p less than or equal to n (2p, 3p, 4p .... kp <= n).
  • Take the first number greater than p in the array that is uncrossed. If there is no such number <= n,then stop. Otherwise, assign this new number in p (which is the next prime), and start from step 3.

Upvotes: 0

ciphermagi
ciphermagi

Reputation: 748

There are complicated mathematical algorithms, like the Sieve of Atkin, that can find primes very quickly, but for your purposes, consider:

Every non-prime number is factorable by primes, if factored far enough.

If you've reached the sqrt(n) and still haven't found it to be factorable, then it won't be factorable, because any number larger than sqrt(n) must be factored alongside a number smaller than sqrt(n) to achieve the number you're looking for.

So test every prime number from 2 to sqrt(n) to see if your n is a prime. If none of the primes between 2 and sqrt(n) are factors of n, then n must be prime.

This should meet with the speed requirements of your assignment.

Upvotes: 1

Related Questions