Prime problem

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).

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:

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

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.

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/tNoLZ7pc9 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

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. )

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

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

-Oscarian

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).

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.

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.

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;
}

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.)

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

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..

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.)

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]

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.

Well, in any case, i optimized the output and it snuck in at 4.6 seconds, so I can walk away (i.e. run screaming) from this problem and move on to the next one. I actually do appreciate your help and patience on this problem. Ultimately I threw out doing any kind of seive and just checked each number in the range by marking as composite any number that taken modulus a prime less than or equal to its root resulted in 0.

While this is technically slower than other methods, it does in fact produce fast enough results.

I am curious though if there is some other method besides printing it to the console that is acceptable? Would it be possible to print it to a specific output file directly from within my program, which should eb much faster than usign printf(). It would be helpful on future problems.

As for the prined output, its because when run in debug mode (i.e. with _WIN32 defined) instead fo takign input from teh console, it randomly generates 10 sets of ranges, so the last one may be lower than the others.

Right. So that explains why you thought your program ran fast. rand() only returns a number up to 32768, so you were only testing your program on very very small inputs. If you had gotten rid of the debugging and just entered the largest possible test case, you would have found that it was running far too slow - a proper sieve would make it run at exactly the same speed as the 1-100000 case. Testing on handpicked test cases is much better than testing on random ones.

In terms of the program itself, you just print to stdout - I was meaning in terms of testing your program. The issue is not that of the outputting taking time - it is that displaying the output takes a long time. If you open up a command prompt, and run your program but directed (via the command prompt) to an output file in the way I mentioned, you will see how long the code actually takes to run, not counting the displaying of the output which isn't part of the program.

For your interest, I've PMed you how to fix your code so it runs fast enough.