[SOLVED] Optimizing C++ prime tester

SkyerSK · 07-14-2011, 11:48 AM

Works for me too, I don't know what's the problem with it on Spoj. I'm going to dig in some SIGABRT mans, maybe I'll find some reason.

ta0kira · 07-15-2011, 03:59 PM

Quote:

Originally Posted by SkyerSK

Works for me too, I don't know what's the problem with it on Spoj. I'm going to dig in some SIGABRT mans, maybe I'll find some reason.

SIGABRT is generally sent intentionally via abort from C (e.g. from libc) when the programmer decides a certain set of circumstances make it unreasonable to continue. It's like an exception, but abort will unset any signal handlers so it will always end the process. You should run it with gdb to see where the program crashes. You might also set signal(SIGABRT, SIG_IGN); and see if you still get SIGABRT.

I was also thinking today it would be interesting to modify the problem slightly so that you output the numbers with a prime number of unique primes in their respective prime factorizations. I'm not sure if there are any number-theory theories related to that, but it would only be slightly more difficult. I might try it just because it will bother me if I don't.
Kevin Barry

PS It might seem arbitrary to find all primes within a certain range of huge numbers; however, finding huge primes is the basis for public key cryptography.

markush · 07-15-2011, 04:05 PM

Quote:

Originally Posted by ta0kira

...
I was also thinking today it would be interesting to modify the problem slightly so that you output the numbers with a prime number of unique primes in their respective prime factorizations. I'm not sure if there are any number-theory theories related to that,
...

Hello Kevin,

this may be very interesting, but I don't seem to understand what you mean. Could you please explain this a little more elaborate, I'm very curious when it comes to number-theory.

Markus

ta0kira · 07-15-2011, 04:10 PM

Quote:

Originally Posted by markush

Hello Kevin,

this may be very interesting, but I don't seem to understand what you mean. Could you please explain this a little more elaborate, I'm very curious when it comes to number-theory.

Markus

For example:

6=2*3; 2 unique prime factors
12=2^2*3; 2 unique prime factors
210=2*3*5*7; 4 unique prime factors
2=2; 1 prime factor

In the above examples, 6 and 12 would meet the criteria, whereas 210 and 2 wouldn't.
Kevin Barry

markush · 07-15-2011, 04:22 PM

Well, I have also tried out the program and modified it. I wanted to find out the "longest" sequence of non-prime numbers up to one million.

Code:

#include <iostream>
using namespace std;

int main()
{
    long int pos, factor;
    long int last_num=1000000, first_num=1;
    int count=0, max=0;

    bool *primes = new bool[last_num+1];

    for (pos=2; pos<(1+last_num/2); pos++)
    {
        if (primes[pos] == 1) 
            continue;
        for (factor=1; pos*factor<=last_num; factor++) 
        {
            if (factor != 1) 
                primes[pos*factor] = 1;
        }
    }
    for (pos=2; pos<last_num+1; pos++) 
    {
        if (primes[pos])  // keine Primzahl
            count++;
        else 
        {
            if (max<count)
                max=count;
            count=0;
        }
    }
    cout << max << endl;
    delete [] primes;
}

the result is 113

Markus

ta0kira · 07-15-2011, 06:38 PM

You should check out Fermat's little theorem and see what creative problems you can come up with. If that's a bit much, maybe start with a little group theory then move on to finite abelian groups.
Kevin Barry

SigTerm · 07-15-2011, 11:43 PM

Quote:

Originally Posted by SkyerSK

Could you please give me some hint about it?

You need another algorithm, you won't beat the time with current one.
When checking if number "N" is prime or not, instead of trying to divide N by every number between 1 and sqrtf(N), try to divide by every prime number between 1 and sqrtf(N).
When iterating through possible divisors (when you test if number is prime) instead of starting at sqrtf(N) and going down to 2, start at 2 and go up to sqrtf(N) - number is singificantly more likely to be divisible by 2 than by its sqare root.
Instead of boolean arrays use stl containers to store prime numbers you found.
Use subroutines instead of of trying to jam everything into main().
Instead of allocating arrays with "new[]" use std::vector.
Don't forget that converting float (result of sqrtf) to int will result in rounding errors.
bool is not int, and C++ is not C. Comparing boolean value with 1 is incorrect.
When you allocate array of type (that does not have a computer) with "new[]", compiler does not initialize it, and it is filled with junk. Not initializing your variables and arrays is a bug.
Learn STL
Get more C++ practice.

markush · 07-16-2011, 04:38 AM

I'm a bit off topic here

Quote:

Originally Posted by ta0kira

You should check out Fermat's little theorem and see what creative problems you can come up with. If that's a bit much, maybe start with a little group theory then move on to finite abelian groups.
Kevin Barry

Well, I came to the program above (longest sequence of non-primary numbers) because I'm reading a book (Discrete Mathmatics) where "Bertrand's Postulate" was mentioned (for any integer n>1 there is at least one primary number p with n < p <= 2n). With the program above and the solution it becomes very clear but the proof is quite difficult (and not given in the book).

Markus

ta0kira · 07-16-2011, 12:28 PM

Quote:

Originally Posted by markush

I'm a bit off topic here

Well, I came to the program above (longest sequence of non-primary numbers) because I'm reading a book (Discrete Mathmatics) where "Bertrand's Postulate" was mentioned (for any integer n>1 there is at least one primary number p with n < p <= 2n). With the program above and the solution it becomes very clear but the proof is quite difficult (and not given in the book).

Markus

(Maybe on topic? It's about math...) The reason it's called a "postulate" is it seems right and hasn't been proven, but it also hasn't been disproven. A famous example is the parallel postulate, which has been proven to be unprovable and undisprovable.
Kevin Barry

markush · 07-16-2011, 12:49 PM

Hello ta0kira,

in this case the postulate has been proven, but not by bertrand who postulated it but by another mathmatician 5 years later, http://en.wikipedia.org/wiki/Bertrand%27s_postulate

More interesting for the problem in this thread seems to be the "Prime Number Theorem" (same book, same page

) which states that one can approximate the number of prime numbers lower than n with

Code:

P(n) ~ n/log(n)

Markus

SkyerSK · 07-17-2011, 02:33 PM

Just came back from vacation, sorry to keep you waiting.
ta0kira: I'll check it, hopefully, I'll come out with something meaningful.
SigTerm: I'll take a look at your advice too, but it will take some time. Btw, more practice of C++: for me, it's not practice, I just started. (If I was skilled enough, I wouldn't have this problem).
markush: I'm very happy to hear any Math conversation, but little jealous that I'm not on same math level and can't read that book right now

Thanks for your help.

SkyerSK · 07-22-2011, 02:52 PM

Duh.. I tried my previous version once again, and it was accepted. (Not sure why..). Nevermind, thanks for your help, problem solved.

markush · 07-22-2011, 02:59 PM

Hello SkyerSK,

I'm happy to read that you found a solution. I found this thread to be very educational, I want to say thanks to the other posters as well.

Markus