1

The Prime Generator requires prime numbers between a certain range.

Input : The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output : For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

My program runs perfectly with this solution but the time limit is exceeded and it isn't accepted as a solution.

I've replaced cin and cout with scanf and printf. I've replaced for loops with while loops and what not. What other measures can I take to speed up my solution?

#include<iostream>
int prime(unsigned long int p)
{ 
    int f=1,i=2;
    while(i<=p/2)
    {
        if(p%i==0)
        {   f=0;    
            break;
        }
        ++i;
    }

    if(f==1)
    {   printf("%d \n",p);
    }
    return 0;
}

int main()
{
    int t, i=0;
    unsigned long int m,n,j;
    scanf("%d",&t);
    while(i<t)
    {
        scanf("%lu%lu",&m,&n);
        for(j=m;j<=n;++j)
        {
            if(j!=1&&j!=0)
                prime(j);
        }
        printf("\n");
        ++i;
    }
    return 0;
}
Jester
  • 51
  • 4
  • please format your code. also include a question in the question, together with a clear problem description, and what you tried so far. – sp2danny Mar 22 '19 at 07:27
  • Okay! I update it. – Jester Mar 22 '19 at 07:44
  • You can hardcode all prime numbers, store them in an array and print all of them from `m` to `n`. – mch Mar 22 '19 at 07:52
  • @mch What if the question asks for primes outside your range? Already Euklid knew that there are infinitely many primes, so your method requires a computer with infinite storage and you need infinite time to pre-compute all primes. Even if the the number range is restricted by using a finite number representation, this becomes a pretty daunting problem. And for small `p` is definitely extremely inefficient. – Walter Mar 22 '19 at 08:16
  • @Walter `1 <= m <= n <= 1000000000` is a requirement, so the array would be a < 1GB header file (9 digit number + `,` and a space * 65M numbers) – mch Mar 22 '19 at 08:57

2 Answers2

1

Your code is inefficient because you’re using a slow algorithm to find primes. Changing a for loop to a while loop probably won’t speed up the code, but changing to a better algorithm will.

A faster algorithm:

There’s a really simple algorithm called the Sieve of Eratosthenes. We start out by making an array of bools. Mark all of them true. This array will let us keep track of which numbers are and aren’t prime. We’re gonna cross out the ones we know aren’t prime (by setting them to false).

  1. Cross out 0 and 1 from the array
  2. Starting with 4, cross out all numbers that are multiples of 2
  3. Starting with 6, cross out all numbers that are multiples of 3
  4. Starting with 10, cross out all multiples of 5
  5. Starting with 14, cross out all multiples of 7
  6. (Continue this process)

Example:

// takes a reference to a vector of bools 
// a vector is a resizable array
void cross_out_multiples(std::vector<bool>& primes, int num) {
    for(int i = num * 2; i < primes.size(); i += num) {
        primes[i] = false;
    }
}

std::vector<int> findPrimes(int max) {
    std::vector<bool> primes(max); // create array with max elements
    for(int i = 0; i < max; ++i) {
        primes[i] = true;
    }
    // 0 and 1 aren’t prime, so we mark them false
    primes[0] = false;
    primes[1] = false;
    // here we mark multiples of n false
    for(int n = 2; n < max; n++) {
        // if a number isn’t prime, we can skip it
        if(not primes[n]) {
            continue;
        }
        // if n squared is bigger than max, we already
        // crossed out all multiples of n smaller than max
        // so we don’t have any more work to do
        if(n * n > max) {
             break;
        }
        // now we just cross out multiples of n
        cross_out_multiples(primes, n);
    }

    // now, take the numbers that are prime:
    std::vector<int> listOfPrimes;
    for(int i = 0; i < max; i++) {
        // if a number is prime, add it to the list
        if(primes[i]) {
            listOfPrimes.push_back(i);
        }
    }
    return listOfPrimes;
}I
Alecto Irene Perez
  • 10,321
  • 23
  • 46
  • 1
    This is the sieve of Eratosthenes. You should not sell this as your own method if it was already invented 2200 years ago. In some parts of this world this behaviour is known as *plagiarism* (and, btw, it doesn't matter if you have re-discovered it independently). – Walter Mar 22 '19 at 08:13
  • I *know* that this is the sieve of Eratosthenes, but it’s not plagiarism because Eratosthenes didn’t write out my c++ code. And I never said it was my method. – Alecto Irene Perez Mar 22 '19 at 08:21
  • I updated my answer to include his name. – Alecto Irene Perez Mar 22 '19 at 08:22
0

Your code is correct, but (very) inefficient. The online judge not only requires correctness, but also efficiency.

The simple scanning algorithm of yours can be immediately made faster by two simple measures:

  1. only test odd divisors

  2. only test divisors up to sqrt(p) (which for large p is much smaller than p/2)

But ultimately learn about the sieve of Eratosthenes.

Walter
  • 44,150
  • 20
  • 113
  • 196