Prime problem

[AntonioCS_sof]

I am using the "Sieve of Eratosthenes" to work this out and I just can't output the primes of the number 1000000000.
The way the algorithm works, is by creating a bool array of half of the number given (in this case 500000000), but every time I try it I get an error saying that there was an unhandled win32 exception [4296] (possibly a segfault).

Anyone know a new direction I can take to resolve this primes problem?

[AntonioCS_sof]

Ok I have found that I have to use the "Sieve of Atkin" instead of the "Sieve of Eratosthenes"
Now I just have to implement this in c++

[oscarian]

I'm working on the prime problem too. I just can't seem to get the logic right.

After some time spent working on the problem I've resorted to cheating by looking up other programs that generate primes.

But it's not helping

-Oscarian

[AntonioCS_sof]

The main problem for me is the be able to go to 100000000.
I use the Eratosthenes algorithm and it requires a bool array with half the limit, and that is what is messing up to code.
Every time I put the number 10000000 it just blows up because of the memory.

[TripleM_sof]

I presume you are talking about PRIME1 (there are lots of prime problems).

Erastothenes is on the right track. If the problem was to generate all primes between 1 and 1000000000 you would indeed run out of time/memory. But you're not asked to do that. The range of numbers is only up to 100000. Think about how you could change the sieve to only cross out numbers in this range.. (theres heaps of earlier threads if you're still stuck, just do a search).

[oscarian]

Yep, working on Prime1 problem. I finally got a method for solving the problem, after spending almost a whole day on the problem. It was really tough getting the logic right, until I read someone's description of how to solve the problem, as follows:

In general the [eratosthenes] Sieve is not really used to get n primes. Rather to get primes in a range from 2 to N. You choose a number N and create and array of numbers from 2 to N. Then you put 2 into your list of primes and then zero all numbers that are multiples of 2 etc.

Then you find the first number that is non-zero and less then and add that to your list of primes and then zero all multiples of that number. repeat until one of two things happen, you reach n primes, or you current prime is greater than sqrt(N)... when that happens add all non-zero numbers to your lest of primes.

[snip]

I didn't use a square root function for my solution, however, I get a "time limit exceeded" when I submitted it.

I would post my code, but I'm not sure that that's acceptable around here?

Or else, may I PM someone to get some advice?

-Oscarian

[TripleM_sof]

Read my post again - you seem to have ignored both parts

As I mentioned, your algorithm works to find all primes from 1 up to a given N. Which is not what this problem asks for.

Let me rephrase the algorithm you have..

Start with a list of 2 to N. Cross of all multiples of 2. Then cross off all multiples of 3. Then cross off all multiples of 5. Continue until your current prime is greater than sqrt(N).

So, to solve this problem, why start with 1 to N? Why not start with the range you actually care about? Your only problem is working out the 2, 3, 5 .. but those numbers definitely don't get too large.

And as mentioned, your same question has been asked at least 5 times before, so while I don't mind answering, you'll get quicker results by searching.

[oscarian]

Sorry TripleM, I should have been more specific. I have used an algorithm that takes any range within the specified requirements - not from the static number 2.

Let me post my code, if it's okay with you, and maybe you'll have a better idea of where I am up to.

The code has two problems, one of which is the speed.

http://codepad.org/tNoLZ7pc has a copy of my code. Let me know if you have any trouble reaching the site.
[edit] Actually my code has some logical errors and omissions, so I am re-writing it from scratch.

The speed, as I mentioned, is one issue. I have done a few searches on the site (before I posted my original post, and after), and wasn't able to find anything specific (that I could also understand and apply) to my particular problem.

The second problem is, for some reason when I use the input "2" (test cases), "1 10" (first test case), "9 10" (second test case), the program generates the primes for the first range 1-10 just fine, but for the second range it outputs the number 5. I'm rather mystified by this problem, and I can only assume it's garbage data left over in my array - but I haven't got a method to work out if that's the case or not.

Sorry to repeat questions that have been asked, but I have tried quite a bit of searching, including some hours spent on google, and have not been able to come up with anything that presents itself to me in a way I can understand.

Maybe you can trigger something in my brain to help me get it!

Cheers-
Oscarian

[TripleM_sof]

Alright, I'm a little flummoxed by what most of this code is trying to do I suggest you try working on a simple version of Eratosthenes first, perhaps by looking at other code samples on the internet and get your code as simple as possible.

For example, a very short piece of code to start with an array representing numbers 1-N, starting with all marked as a possible prime and marking every second one as not prime would be something like:

for (int i=1; i<=N; i++) array[i] = true;
for (int i=2; i<=N; i+=2) array[i] = false;

I have a feeling about 30 lines of your code tries to accomplish that (will need another line or two to account for the different range), with a few bugs in it, but I'm not quite sure. Probably a good place to start though.

(PS - at least one reason your code times out is:

for (int x = 3; x <= secondNum[i]; x++)

Even if you just ran this loop once, it would probably time out, let alone 50000 times. )

[oscarian]

My new code:
http://codepad.org/8ueH2jcm

Still exceeds time limit, though. But I'm pretty proud of what I've acheived so far, and it's been fun too!

-Oscarian

[TripleM_sof]

I guess the main issue is that you aren't implementing a sieve at all, just testing if each number is prime by dividing by 2 and all odd numbers less than the sqrt. That is too slow for this problem; you really need to implement a sieve (where you do no divisions at all).

[abachler]

I implimented sieve of arasthosenes and it still will not complete in the given time. Even rabin miller fails, which leads me to the conclusion that the problem isnt about prime numbers at all, but an Input output optimization problem, you should change the name and description of the problem, since it only incidentally has anything to do with prime numbers.

[TripleM_sof]

abachler has been PMed with his mistake. The problem is definitely about prime numbers, and nothing to do with fast input/output

Rabin Miller is fast for large numbers, but slower than a simple sieve on this problem, which is why that method will and should time out.

[abachler]

No actually, rewriting the code, and reducign the actual calculation portion to 125 mS, only served to demonstrate, that it is beyond a doubt an I/O problem. 125 ms to do teh calculation, and it fails due to time exceeded while printing the answer.

Here is the code that I used. EVEN WITH NO OUTPUT GENERATED AT ALL EXCEPT A SINGLE CARRIAGE RETURN< IT REPORTS TIME EXCEEDED.
So, either there is somethign serioulsy messed up withthe system on which it is running, or that system is so low performance that I really see no point in submitting any new code. As I said, this runs in 125 ms on my system, so to exceed 6 seconds on the target system it must be a 66 Mhz system.

spoj.pl/files/src/2140511/

#ifdef _WIN32
#define DEBUG_IT
#endif
#ifdef DEBUG_IT
#include <windows.h>
#endif
#include <stdio.h>
#include <math.h>
#include <malloc.h>
int Input_Count = 0;
int x;
int Divisors[100000];
int* PrimesA;
int* PrimesB;
int* Primes1;
int* Primes2;
int* PrimesTemp;
int* Primes;
void genprimes(int,int);
void CalcDivisors();
int isPrime(int);
int mm[10];
int nn[10];
int _mm[10];
int _nn[10];
int MaxRoot = 0;
void Miller_Rabin(int*,int);
void Sieve_of_Eratosthenes(int*,int);
int main(void){
    Primes = (int*)malloc(100000 * sizeof(int));
    int* Zero = (int*)malloc(100000 * sizeof(int));
    


CalcDivisors();
#ifndef DEBUG_IT
    scanf("%d" , &Input_Count);
#else 
    DWORD Start = GetTickCount();
    Input_Count = 10;
#endif
    for(int x = 0;x<Input_Count;x++){
#ifndef DEBUG_IT
        scanf("%d %d" , &mm[x] , &nn[x]);
#else 
        mm[x] = rand();
        nn[x] = mm[x]+100000;
#endif
        }
    for(int x = 0;x<Input_Count;x++){
    for(int z = 0;z<100000;z++) Primes[z] = 0;
    for(int y = mm[x];y<nn[x]+1;y++){
        Primes[y-mm[x]] = y;
        }
    //Miller_Rabin(Primes , nn[x] - mm[x] + 1);
    Sieve_of_Eratosthenes(Primes , nn[x] - mm[x] + 1);
    for(int y = mm[x];y<nn[x]+1;y++){
        //if(Primes[y-mm[x]] != 0) printf("%d\n" , Primes[y-mm[x]]);
        }
    printf("\n");
    }
#ifdef DEBUG_IT
    printf("Elapsed Time - %d\n" , GetTickCount() - Start);
#endif
    return 0;
}
int isPrime(int Prime){
    int Root = 1;
    while((Prime / Root) > Root) Root++;
for(int Test = 1;Divisors[Test] <= Root;Test++){ // skips the 2
    if(Prime % Divisors[Test] == 0) return 0;
    }
return 1;
}
void CalcDivisors(){
    int Index = 4;
    Divisors[0] = 2;
Divisors[1] = 3;
Divisors[2] = 5;
Divisors[3] = 7;

for(int x = 11;x<31623;x+=2){
    if(isPrime(x)){
        Divisors[Index] = x;
        Index++;
        }
    }
MaxRoot = Index;
return;
}
void Sieve_of_Eratosthenes(int* Numbers , int Count){
    if(Numbers[0] == 1) Numbers[0] = 0; // a kludge for the SPOJ entry, assumes a little
    // the global array Divisors[] is defined and contains all the factors that can possibly be needed
// MaxRoot is the maximum index into Divisors that is valid + 1
int Root = sqrt((double)Numbers[Count-1]);
int Test = 0;
int Start = Numbers[0];
int temp = 0;



while(Divisors[Test] <= Root){
    temp = Start / Divisors[Test];
    for(int x = 0;x<Count;x++){
        while(Numbers[x] > temp) temp += Divisors[Test];
        if(Numbers[x] == temp) Numbers[x] = 0;
        }
    Test++;
    }
            

return;
}
int Miller_Rabin_Set[] = { 2 , 7 , 31 , 61 , 73 };
void Miller_Rabin(int* Numbers , int Count){
    int n , s , d , a;
    int k = 5;

for(int x = 0;x<Count;x++){
    n = Numbers[x];
    
    if(n & 1 ){ // only process odd numbers
        printf("%d\n" , n);
        // 31 73 or 2 7 61
        s = 0;
        n--;
        while(!((n / (1 << s)) & 1)){
            s++;
            //printf("%d\n" , s);
            }
        d = n / (1 << s);
        n++;
        for(int y = 0;y<k;y++){
            a = 1;
            for(int z = 0;z<d;z++) a = (a * Miller_Rabin_Set[z]) % n;
            
            if(a == 1 || a == n) goto end_y;
            for(int r = 1;r<s;r++){
                a = (a * a) % n;
                if(a == 1){
                    Numbers[x] = 0;
                    goto end_x;
                    }
                if(a == n) goto end_y;
                Numbers[x] = 0;
                goto end_x;
                }
end_y: // end of the y loop
                n++;
                }
end_x: // end of the x loop
            n++;
            } else Numbers[x] = 0;
        }
    return;
}

[TripleM_sof]

If you insist on believing that it is to do with input and output, then perhaps you should go and do a different problem. I repeat, your algorithm is at fault here, NOT the speed of reading input.

Perhaps you should reread what you actually wrote.. you removed printing output. And you still got TLE. If input/output is the problem, then you must believe scanning in 20 numbers takes several seconds?

Since your code gets TLE without printing any output, you've just proved your algorithm is at fault.

If I run your code on the sample input, I get the wrong answer. If I run it on the largest possible input, your problem thinks for several seconds (more than the time limit), then crashes, since in the largest possible case your loop

while(Divisors[Test] <= Root){

will never end (the last 'Divisors' element is <= the root, and the next one is 0, and you'll go out of bounds).

If I fix the latter problem in your code, and run it on a SINGLE test case of maximum size, it takes 13 seconds. And my computer is quite fast.

You still haven't implemented a proper sieve. I took your exact code, changed the sieve method to actually sieve rather than run through all numbers for all divisors, and it runs the largest test case in about 0.1 seconds.

If you still don't believe me, I can send you the corrected version of your code, though that means you would never have come up with a fast enough ALGORITHM yourself.

(In fact, I've submitted the fixed Sieve method to SPOJ, and all 10 cases were accepted with a total time of 0.19 seconds.)

[abachler]

Its not the INPUT that causes teh timeout, its the OUTPUT, since the problem requires printing thousands of numbers to stdout. As stated, this algorith runs in 125 ms on my system, and with output requires over 2 seconds, thereofr the output is the rpedominant portion of this problem. Explain to me then how you figure it is NOT an I/O problem?

    while(Divisors[Test] <= Root){
        temp = Start / Divisors[Test];
        for(int x = 0;x<Count;x++){
            while(Numbers[x] > temp) temp += Divisors[Test];
            if(Numbers[x] == temp) Numbers[x] = 0;
            }
        Test++;
        }

end when Divisors[Test] exceeds the root of the maximum number in the range. It ends on my system, so therefor it ends on teh target system. Even upon changing the Divisors to include more than enough divisors (up to 65535) it still produces TLE

[TripleM_sof]

I already told you in my last post. You said commenting out the output gives a TLE, so the algorithm is the thing that causes the time problem. Your current algorithm also has bugs that give the wrong answer and cause it to run for a long time before crashing. And fixing the bugs and submitting gives accepted in 0.19 seconds.

Read my last post again..

[TripleM_sof]

Replying to your edit - I am trying to help you here you know When I said that loop doesn't end, I wasn't mistaken.

You previously had stored values in all positions up to Divisors[31622]. When you have input 999900000 1000000000, you will calculate Root = 31622. Thus, your loop will proceed as follows

Divisors[0] <= 31622.. yes
Divisors[1] <= 31622.. yes
..
Divisors[31621] <= 31622.. yes
Divisors[31622] <= 31622.. yes
Divisors[31623] <= 31622.. yes, because you haven't stored anything in Divisors[31623], it is initialised to 0
..
Divisors[99999] <= 31622.. yes
Divisors[100000] <= 31622.. absolutely anything can happen here when you access memory out of range. Usually it would crash, on some computers you may get lucky and have it not crash.

Now that you've fixed that, you just have to fix the other bug in the sieve and fix the entire sieve itself and you'll get accepted.

(And I seriously can't believe you can run 10 cases of 999900000 1000000000 with such a slow algorithm in 0.125 seconds on your computer.)

[abachler]

Sorry, im callign bullshit onthis one. Since it stops runnign the seive as soon as it has reached a divisor that exceeds the root of the maximum number in range, and since it calculates divisors up to 65535 in my most recently submitted code it obviously is not a 'going out of bounds problem.

Don't modify the code, run it as it is and give me a screen shot fo the output showign the total time elapsed on your system where it shows it exceeds the time limit, because I have such a screenshot right here...

The one on the left is with output, the one on teh right is with calculations only.
actually lookign at that output there are errors, but the judge shoudl report wrogn answer not TLE.

[attachment=0]PRIME!_Output.JPG[/attachment]

[TripleM_sof]

May I ask why your program is printing out numbers less than 125000? The last output should be 999999937.

Are you sure you are running your program on the largest input?

PS - when testing in terms of time, you should never print your output to stdout, as the command prompt can't handle that much output. You should pipe the output to a file instead, like SPOJ does (yourprogram > out.txt in the command prompt). The time taken for the output should be milliseconds, but that explains why you think the output itself is slow.