0

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

DrummerB
  • 39,814
  • 12
  • 105
  • 142
Luka
  • 187
  • 3
  • 9
  • Skip even numbers. Check for prime number by dividing upto the square root of the number instead of its half. – sgarizvi Mar 22 '14 at 20:45
  • 1
    Your program is of `O(n^3)`. – haccks Mar 22 '14 at 20:53
  • 3
    It would be a challenge to write a slower algorithm than yours. There are many many many posts online, at SO and elsewhere, that discuss efficient methods for generating primes ... did you look for *any* of them? – Jim Balter Mar 22 '14 at 21:04
  • see http://stackoverflow.com/a/20749428/849891 and the links therein. – Will Ness Mar 22 '14 at 23:02
  • possible duplicate of [Prime Generator Algorithm](http://stackoverflow.com/questions/20744025/prime-generator-algorithm) – Will Ness Mar 22 '14 at 23:26

2 Answers2

1

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.

ciphermagi
  • 747
  • 3
  • 14
  • He has to generate all primes over a range of 100,000 integers, so the sieve is the only way to go. The Sieve of Atkin will work but there are simpler sieves. http://en.wikipedia.org/wiki/Prime_number_sieve – user3386109 Mar 22 '14 at 21:04
  • The sieve is *not* the only way to go. I generated every prime from 2 to 10^12 in less than 10 seconds with my algorithm. I'm certain that primes from 2 to 10^6 will be *much* faster. – ciphermagi Mar 22 '14 at 21:05
  • "2 to 10^6" -- That's not relevant. The problem is to generate the primes in *any* 10^5 window below 10^9. I think the Sieve of Atkin is particularly good for intervals, but there are variants of the Sieve of Demosthenes that also are good. – Jim Balter Mar 22 '14 at 21:09
  • @JimBalter Actually, the problem is any 10^6 window below 10^10. As I'm sure you're aware, the majority of time spent in my algorithm will be in the final exponent. I'm still confident that, given the parameters, my algorithm will still perform within the appropriate time. – ciphermagi Mar 22 '14 at 21:11
  • No, I believe I have it right: 100000 = 10^5, 1000000000 = 10^9 – Jim Balter Mar 22 '14 at 21:13
  • @JimBalter Yes; even faster. I liked your edit, though, changing what you originally said from 10^6 window below 10^12. – ciphermagi Mar 22 '14 at 21:15
  • 1
    My original was from naively copying the numbers from your comment that I responded to -- I had mistakenly assumed that you had correctly used the OP's numbers. I quickly made the edit -- *before* I wrote "I have it right". In any case, 10^6 and 10^10 or 10^12 are wrong. – Jim Balter Mar 22 '14 at 21:22
  • Oh, no...that confusion probably came from my original testing, in which I used upper bounds that I came up with myself, disregarding the bounds of the OP. – ciphermagi Mar 22 '14 at 21:23
  • And the secondary mistake is due to my trying to count zeroes while not wearing glasses. – ciphermagi Mar 22 '14 at 21:24
  • I have an advantage over you -- I'm nearsighted. :-) – Jim Balter Mar 22 '14 at 21:25
0

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.
haccks
  • 104,019
  • 25
  • 176
  • 264