CODEWITHSUNDEEP
calgorithmprimes
user6927987
user6927987

Reputation:

Reduce execution time of prime number generator

I have to print numbers between two limits n and m, t times.

I created t variable, and two pointers n, m that points to reserved blocks of memory for t integer values.

I use pointers instead of array to do faster operations.

Outer for loop iterates for every test cases and increasing m and n pointers.

Inner for loop prints primes from m[i] to n[i].

Code

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

int is_prime(int);

int main(void) {
    
    int t;
    int *n = malloc(sizeof(int) * t);
    int *m = malloc(sizeof(int) * t);

    scanf("%d", &t);
    for (int i = 0; i < t; i++, m++, n++) {
        scanf("%d %d", &m[i], &n[i]);
        for (int j = m[i]; j <= n[i]; j++) {
            if (is_prime(j)) {
                printf("%d\n", j);
            }
        }
        if (i < t - 1) printf("\n");
    }

    return 0;
}

int is_prime(int num)
{

    if (num <= 1) return 0;
    if (num % 2 == 0 && num > 2) return 0;
     
    for(int i = 3; i < num / 2; i+= 2){
         if (num % i == 0)
             return 0;
    }
    
    return 1;
}

Problem: http://www.spoj.com/problems/PRIME1/

Code is correctly compiling on http://ideone.com but I'm giving "time limit exceeded" error when I'm trying submit this code on SPOJ. How can I reduce execution time of this prime number generator?

Upvotes: 1

Views: 791

Answers (4)

neilharia7
neilharia7

Reputation: 149

You can even do it without using pointers or arrays 

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

int is_prime(long n){
    if (n == 1 || n % 2 == 0)
        return 0;
    if (n == 2)
        return 1;
    for (long i = 3; i <= sqrt(n); i += 2) {
        if(n % i == 0)
            return 0;
    }
    return 1;
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        long n, m;
        scanf("%ld %ld",&n,&m);

        for (long i = n; i <= m; i++) {
            if (is_prime(i) == 1)
            printf("%ld\n",i);
        }
    }
    return 0;
}

Upvotes: 0

Cpp plus 1
Cpp plus 1

Reputation: 1010

I know that you are looking for algorithm improvements, but the following technical optimizations might help:

If you are using Visual Studio, you can use alloca instead of malloc, so that n and m go in the stack instead of the heap.

You can also try to rewrite your algorithm using arrays instead of pointers to put n and m in the stack.

If you want to keep using pointers, use the __restrict keyword after the asterisks, which alerts the compiler that you don't make references of the two pointers.

Upvotes: 0

perror
perror

Reputation: 7386

There are several ways to improve the primality check for an integer n. Here are a few that you might find useful.

  1. Reduce the number of checks: A well known theorem is giving the fact that if you want to look for factors of n, let say n = a * b, then you can look for a divisor between 1 and sqrt(n). (Proof is quite easy, the main argument being that we have three cases, either a = b = sqrt(n), or we have a < sqrt(n) < b or b < sqrt(n) < a. And, whatever case we fall in, there will be a factor of n between 1 and sqrt(n)).

  2. Use a Sieve of Eratosthenes: This way allows to discard unnecessary candidates which are previously disqualified (see Sieve of Eratosthenes (Wikipedia))

  3. Use probabilistic algorithms: The most efficient way to check for primality nowadays is to use a probabilistic test. It is a bit more complex to implements but it is way more efficient. You can find a few of these techniques here (Wikipedia).

Upvotes: -1

einpoklum
einpoklum

Reputation: 131445

As @Carcigenicate suggests, you're exceeding the time limit because your prime generator is too slow; and it's too slow since you're using an inefficient algorithm.

Indeed, you should not simply test each consecutive number for primality (which, by the way, you're also doing ineffectively), but rather rule out multiple values at once using known primes (and perhaps additional primes which you compute). For example, you don't need to check multiples of 5 and 10 (other than the actual value 5) for primality, since you know that 5 divides them. So just "mark" the multiples of various primes as irrelevant.

... and of course, that's just for getting you started, there are all sort of tricks you could use for optimization - algorithmic and implementation-related.

Upvotes: 2

Related Questions