3

I've been trying to solve the SPOJ problem of Prime number Generator Algorithm.

Here is the question

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

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.

It is very easy, but the online judge is showing error, I didn't get what the problem meant by 'test cases' and why that 1000000 range is necessary to use.

Here is my code.

#include<stdio.h>

main()
{
int i, num1, num2, j;
int div = 0;
scanf("%d %d", &num1, &num2);
for(i=num1; i<=num2; i++)
  {
    for(j=1; j<=i; j++)
    {
      if(i%j == 0)
      {
        div++;
      }
    }
    if(div == 2)
    {
     printf("%d\n", i);
    }
    div = 0;
  }
  return 0;
}
Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
user3129609
  • 57
  • 1
  • 2
  • Read up on CPPunit - See http://sourceforge.net/apps/mediawiki/cppunit/index.php?title=Main_Page – Ed Heal Dec 23 '13 at 12:55
  • 1
    Use segmented seive ! – Kaustav Ray Dec 23 '13 at 13:01
  • `j` starts from 1, and all numbers `%1` give 0... Then you don't have to do all numbers up to *i* (sqrt(i) is enough). Then you have plenty of algos doing this on the Net. – Déjà vu Dec 23 '13 at 13:01
  • @ring0 Yes, it was my mistake sqrt(i) is enough, but all numbers %1 give 0, the definition of prime, prime is number which is divisible by one and itself, so i have to do it until i not upto sqrt(i). The number range is small, so the numbers will be processed fast, no problem in that. I have written this algorithm on my own, this is the simplest as compared to other algorithms on the net – user3129609 Dec 23 '13 at 13:04
  • As I have seen the question, seive of Eratosthenes won't work for this data. You have to use segmented seive. http://sweet.ua.pt/tos/software/prime_sieve.html – Kaustav Ray Dec 23 '13 at 13:09
  • You might look into this ! http://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes – Kaustav Ray Dec 23 '13 at 13:10
  • You should use unsigned long long instead of int. – Abhishek Bansal Dec 23 '13 at 13:34
  • @KaustavRay segmented sieve is not need here at all. one contiguous sieve of the core from 2 to 32000 is enough; then each separate offset segment can be sieved using the core primes. "segmented sieve" refers to sieving of a succession of segments, one after another, without definite top limit. Here, the top limit is known in advance, and its square root is very small. – Will Ness Dec 23 '13 at 19:11
  • @Will Ness, Thanks ! I understand now ! Actually I got the problem submitted with offline storage of all primes :D ! – Kaustav Ray Dec 24 '13 at 03:06
  • [Prime Generator(spoj)](http://stackoverflow.com/questions/28122420/prime-generatorspoj/39664186#39664186) Please have a look at my answer here: http://stackoverflow.com/a/39664186/6436907 – Uddalak Bhaduri Sep 23 '16 at 15:23

8 Answers8

4

I can't comment on the alogirthm and whether the 100000 number range allows optimisations but the reason that your code is invalid is because it doesn't seem to be parsing the input properly. The input will be something like:

2
123123123 123173123 
987654321 987653321

That is the first line will give the number of sets of input you will get with each line then being a set of inputs. Your program, at a glance, looks like it is just reading the first line looking for two numbers.

I assume the online judge is just looking for the correct output (and possibly reasonable running time?) so if you correct for the right input it should work no matter what inefficiencies are in your algorithm (as others have started commenting on).

Chris
  • 27,210
  • 6
  • 71
  • 92
2

The input begins with the number t of test cases in a single line (t<=10) you haven't got test cases in your programm. Its wrong And sorry for my English

2 - //the number of test cases
1 10 - // numbers n,m
3 5 - // numbers

Your programm will work only in first line.

venimus
  • 5,907
  • 2
  • 28
  • 38
user5450071
  • 31
  • 1
2
#include <stdio.h>
#include <math.h>
int main()
{
    int test;
    scanf("%d",&test);
    while(test--)
    {
        unsigned int low,high,i=0,j=2,k,x=0,y=0,z;
        unsigned long int a[200000],b[200000];
        scanf("%d",&low);
        scanf("%d",&high);
        for(i=low;i<=high;i++)
            a[x++]=i;
        for(i=2;i<=32000;i++)
            b[y++]=i;
        i=0;
        while(b[i]*b[i]<=high)
        {
            if(b[i]!=0)
            {
                k=i;
                for(;k<y;k+=j)
                {
                    if(k!=i)
                    {
                        b[k]=0;
                    }
                }
            }
            i+=1;j+=1;
        }
            for(i=0;i<y;i++)
            {
                if(b[i]!=0 && (b[i]>=low && b[i]<=sqrt(high)))
                    printf("%d\n",b[i]);
            }
            int c=0;
            for(i=0;i<y;i++)
            {
                if(b[i]!=0 && (b[i]>=1 && b[i]<=sqrt(high)))
                    b[c++]=b[i];
            }
            int m=a[0];
            for(i=0;i<c;i++)
            {
                z=(m/b[i])*b[i];k=z-m;
                if(k!=0)
                    k += b[i];
                for(;k<x;)
                {
                    if(a[k]!=0)
                    {
                        a[k]=0;
                    }
                    k+=b[i];
                }
            }
            for(i=0;i<x;i++)
            {
                if(a[i]!=0 && (a[i]>=2 && a[i]<=(high)))
                    printf("%d\n",a[i]);
            }
        printf("\n");
    }
    return 0;
}
Uddalak Bhaduri
  • 83
  • 8
  • @mhatch I am using a segmented Sieve of Eratosthenes method. To know how this method works refer to this link: https://turjachaudhuri.wordpress.com/2013/12/14/spoj-prime-1-segmented-sieve-of-eratosthenes/ – Uddalak Bhaduri Sep 26 '16 at 17:11
1

For such small numbers you can simply search for all primes between 1 and 1000000000.

Take 62.5 mByte of RAM to create a binary array (one bit for each odd number, because we already know that no even number (except of 2) is a prime).

Set all bits to 0 to indicate that they are primes, than use a Sieve of Eratosthenes to set bits to 1 of all number that are not primes.

Do the sieve once, store the resulting list of numbers.

MrSmith42
  • 9,961
  • 6
  • 38
  • 49
  • 1
    I think simple Seive of Eratosthenes would exceed time limit of the given question. – Kaustav Ray Dec 23 '13 at 13:07
  • In my experience, if you want to finish executing in under a minute, a sieve is only practical for maximums lower than about ten million. I suspect going up to a billion would take much longer. – Kevin Dec 23 '13 at 13:07
  • 1
    You can create do the Sieve of Eratosthenes before knowing n and m. So the creation time is not part of the time needed to answer the question which primes are between n and m. Creating the sieve can be done offline (and needs to be done only once independent of all n,m requests). – MrSmith42 Dec 23 '13 at 14:14
  • 1
    Do the sieve once, store the resulting list of numbers. – Jesan Fafon Dec 23 '13 at 16:14
  • Use template metaprogramming to produce the numbers, moving the problem to compile time ;-). Reminds me of my former boss printing a mandelbrot set on a PostScript printer; the print job was a few lines of PostScript computing the set *on the printer*. – Peter - Reinstate Monica Aug 27 '19 at 16:32
1

To find primes between m,n where 1 <= m <= n <= 1000000000, n-m<=100000, you need first to prepare the core primes from 2 to sqrt(1000000000) < 32000. Simple contiguous sieve of Eratosthenes is more than adequate for this. (Having sieved the core bool sieve[] array (a related C code is here), do make a separate array int core_primes[] containing the core primes, condensed from the sieve array, in an easy to use form, since you have more than one offset segment to sieve by them.)

Then, for each given separate segment, just sieve it using the prepared core primes. 100,000 is short enough, and without evens it's only 50,000 odds. You can use one pre-allocated array and adjust the addressing scheme for each new pair m,n. The i-th entry in the array will represent the number o + 2i where o is an odd start of a given segment.

See also:

A word about terminology: this is not a "segmented sieve". That refers to the sieving of successive segments, one after another, updating the core primes list as we go. Here the top limit is known in advance and its square root is very small.

The same core primes are used to sieve each separate offset segment, so this may be better described as an "offset" sieve of Eratosthenes. For each segment being sieved, only the core primes not greater than its top limit's square root need be used of course; but the core primes are not updated while each such offset segment is sieved (updating the core primes is the signature feature of the "segmented" sieve).

Community
  • 1
  • 1
Will Ness
  • 70,110
  • 9
  • 98
  • 181
1
int num; 
bool singleArray[100000]; 
static unsigned long allArray[1000000]; 
unsigned long nums[10][2]; 

unsigned long s;       
long n1, n2;
int count = 0; 
long intermediate; 


scanf("%d", &num);

for(int i = 0; i < num; ++i) 
{
    scanf("%lu", &n1);  
    scanf("%lu", &n2); 
    nums[i][0] = n1;   
    nums[i][1] = n2;   
}


for(int i = 0; i < 100000; ++i)  
{
    singleArray[i] = true;
}

for(int i = 0; i < num; ++i) 
{
    s = sqrt(nums[i][1]);
    for(unsigned long k = 2; k <= s; ++k)  
    {
        for (unsigned long j = nums[i][0]; j <= nums[i][1]; ++j) 
        {
            intermediate = j - nums[i][0];
            if(!singleArray[intermediate]) 
            {
                continue;
            }
            if((j % k == 0 && k != j) || (j == 1))      
            {
                singleArray[intermediate] = false;
            }
        }
    }


    for(unsigned long m = nums[i][0]; m <= nums[i][1]; ++m) 
    {
        intermediate = m - nums[i][0];
        if(singleArray[intermediate])  
        {
            allArray[count++] = m;
        }
    }

    for(int p = 0; p < (nums[i][1] - nums[i][0]); ++p)
    {
        singleArray[p] = true;
    }
 }


for(int n = 0; n < count; ++n)
{
    printf("%lu\n", allArray[n]);
}

}

user5450071
  • 31
  • 1
0

Your upper bound is 10^9. The Sieve of Eratosthenes is O(N loglogN) which is too much for that bound.

Here are a few ideas:

Faster primality tests

The problem with a naive solution where you loop over the range [i, j] and check whether each number is prime is that it takes O(sqrt(N)) to test whether a number is prime which is too much if you deal with several cases.

However, you could try a smarter primality testing algorithm. Miller-Rabin is polynomial in the number of bits of N, and for N <= 10^9, you only need to check a = 2, 7 and 61.

Note that I haven't actually tried this, so I can't guarantee it would work.

Segmented sieve

As @KaustavRay mentioned, you could use a segmented sieve. The underlying idea is that if a number N is composite, then it has a prime divisor that is at most sqrt(N).

We use the Sieve of Eratosthenes algorithm to find the prime numbers below 32,000 (roughly sqrt(10^9)), and then for each number in the range [i, j] check whether there is any prime below 32,000 that divides it.

By the prime number theorem about one in log(N) numbers are prime which is small enough to squeeze in the time limit.

sebii
  • 506
  • 2
  • 6
  • this is incorrect. [SoE is perfectly capable](http://stackoverflow.com/a/20749428/849891) of dealing with this problem. In fact, a submission of mine ran for 0.01 seconds at SPOJ. And sieve of Eratosthenes tests no divisions, it's "trial division" that does that, and it is much slower. For comparison, I tried it too (using unrolled 2-3-wheel) and it ran for 0.21 seconds at SPOJ. Also, this is not a "segmented sieve" either, it is an *offset* sieve as we do *not* sieve consecutive segments one after another here. – Will Ness Nov 03 '14 at 10:24
0
#include <iostream>
using namespace std;

int main() {

    // your code here
unsigned long int m,n,i,j;int N;
cin>>N;
for(;N>0;N--)
{
    cin>>m>>n;
    if(m<3)
        switch (n)
        {
            case 1: cout<<endl;continue;
            case 2: cout<<2<<endl;
                    continue;
            default:cout<<2<<endl;m=3;
        }
    if(m%2==0) m++;        
    for(i=m;i<=n;i+=2)
    {  
        for(j=3;j<=i/j;j+=2)
            if(i%j==0)
                {j=0;break;}
        if(j)
        cout<<i<<endl;
    }
        cout<<endl;

}return 0;}
Moriarity
  • 1