Блог пользователя Betlista

Автор Betlista, 13 лет назад, По-английски

It is easy to find if some number (say N) is prime or not — you simply need to check if at least one number from numbers lower or equal sqrt(n) is divisor of N. This can be achieved by simple code:

boolean isPrime( int n ) {
    if ( n == 1 ) return false; // by definition, 1 is not prime number
    if ( n == 2 ) return true; // the only one even prime
    for ( int i = 2; i * i <= n; ++i )
        if ( n%i == 0 ) return false;
    return true;
}

So it takes sqrt(n) steps to check this. Of course you do not need to check all even numbers, so it can be "optimized" a bit:

boolean isPrime( int n ) {
    if ( n == 1 ) return false; // by definition, 1 is not prime number
    if ( n == 2 ) return true; // the only one even prime
    if ( n%2 == 0 ) return false; // check if is even
    for ( int i = 3; i * i <= n; i += 2 ) // for each odd number
        if ( n%i == 0 ) return false;
    return true;
}

So let say that it takes 0,5*sqrt(n) steps. That means it takes 500.000.000 steps to check that 1.000.000.007 is a prime.

But there is great idea — why to "do not check even numbers". This idea can be extended to: "do not divide N by candidate numbers, but mark the prime multiples as 'not prime'".

In other words: if we know about some number p, taht it is prime, we mark all multiples (2*p, 3*p, 4*p, ...) as not a prime. To implement this we need limit (max number we care about), let say it is 120 (because there is nice animation of algorithm on wikipedia).

In Java I'm using this code:

    private static final boolean[] isPrime = new boolean[121];
    static {
        Arrays.fill( isPrime, true ); // first we assume all numbers are primes if not shown otherwise
        isPrime[ 0 ] = false; // zero is not prime - it'is not greater than 1
        isPrime[ 1 ] = false; // one is not prime - it'is not greater than 1
        for ( int p = 2; p < isPrime.length; ++p ) {
            if ( isPrime[ p ] ) {
                for ( int m = 2; m * p < 121; ++m ) {
                    isPrime[ m * p ] = false;
                }
            }
        }
    }

Now, you can answer the question "is n prime" in constant time. Of course problems like this one are so simple, that you won't see it as problems, but it is subproblem of some more diffucult problem often.

You can memorize the primes too. And while it holds that even number multiply by whatever is even (and there is just one even prime number), you can skip all even m:

    private static final int LIMIT = 121;
    private static final boolean[] isPrime = new boolean[LIMIT + 1];
    private static ArrayList<Integer> primes = new ArrayList<Integer>();
    static {
        Arrays.fill( isPrime, true ); // first we assume all numbers are primes if not shown otherwise
        isPrime[ 0 ] = false; // zero is not prime - it'is not greater than 1
        isPrime[ 1 ] = false; // one is not prime - it'is not greater than 1
        isPrime[ 2 ] = true; // only one even prime
        primes.add( 2 );
        for ( int i = 4; i <= LIMIT; i += 2 ) {
            isPrime[ i ] = false;
        }
        for ( int p = 3; p <= LIMIT; p += 2 ) {
            if ( isPrime[ p ] ) {
                primes.add( p );
                for ( int m = 3; m * p < LIMIT; m += 2 ) {
                    isPrime[ m * p ] = false;
                }
            }
        }
    }

Maybe you would like to have primes in array instead of List — you can use toArray(int []) method or you find out how many prime numbers (lower than limit) there are. That's why I'm adding this table here:

limit # of primes last lower prime first greater prime
120 30 113 (30th) 127 (31st)
1.000 168 997 1009
10.000 1229 9973 10007
100.000 9592 99991 100003
1.000.000 78489 999983 1000003
10.000.000 664579 9999991 10000019
100.000.000 5761455 99999989 100000007

There exist other sieves, also there are other optimizations possible (for example isPrime array do not need to contain even numbers).

Problems where you cen practise:

edit: problems added

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

Instead of taking the trouble of writing so much you could have just given the link. Here's LightOJ tutorial about the sieve ->LINK

Anyways +1 for your efforts :-)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    Who will read this at LightOJ? One can't read anything here without registration, and this is really weird.

»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

A small and common mistake.

The limit in Sieve of Eratosthenes is square root of N in the first for, not N.

int lim=(int)Math.sqrt(LIMIT)+1;
  for ( int p = 3; p <=lim; p += 2 ) {
            if ( isPrime[ p ] ) {
                primes.add( p );
                for ( int m = 3; m * p < LIMIT; m += 2 ) {
                    isPrime[ m * p ] = false;
                }
            }
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    another "mistake", or optimization for ( int m = 3; => for ( int m = p;

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks, idea is correct, for marking primes in isPrime array this approach is correct, but in this implementation primes list does NOT contain primes greater than sqrt(LIMIT) + 1. It is required to iterate over the array from lim to LIMIT for addition of all primes.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There exists a better version of sieve whose runtime is linear, here's the tutorial (translated to English using google translator). You can make it faster and cache friendly using some bitwise tricks (check the following link).

There is also another variant of sieve which is known as segmented sieve.

Thanks :)

  • »
    »
    12 лет назад, # ^ |
    Rev. 17   Проголосовать: нравится +3 Проголосовать: не нравится

    You can also optimize the sieve further by starting at the number the first for-loop is at, so start at 3*3, then 5*5, 7*7 because 5*3 has already been taken care of by the 3's and 7*3 and 7*5 has already been declared not prime by the 5 and 3.

    It is a small optimization, but can possibly speed up the process a you get to larger values n

    E: Note this works accurately only for languages for with an arbitrary precision library, otherwise, because of c/c++ lack of large integer types, this tends to not work very well

    E2: Nvm, If you use unsigned long long, it should work

    With Optimization:

    $ time ./auto
    Primes below 100000000 is 5761455
    
    real	0m5.435s
    user	0m5.332s
    sys	0m0.068s
    

    Without

    time ./auto
    Primes below 100000000 is 5761455
    
    real	0m10.143s
    user	0m10.045s
    sys	0m0.056s
    

    As you can see, time difference is very apparent the larger the values you are looking for and all it took was one variable change to get these faster results :D

»
3 года назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

Thanks for the problem set in the end. The last one was a nice problem 109B Colliders

Also, there is another concept called segmented sieve a sort of modification to the basic one. It's a memory-efficient algorithm to compute primes between two large numbers.

These GFG videos explained great!

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please answer how can i do Colliders... Regards

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hint : every prime factor will be mapped to any one single element only

    Hint : use a set to have live element and a map to store the prime factors of those involved in the live set

    Use a map to store the prime factors of all those which got success

    if some prime factor is mapped to the same then it is already on

    else then conflict with the number to which the factor is mapped.

    in case of success map the factor to the parent element and insert into the live set

    in case of erase

    if live set have that element erase from the set and map its factors to 0

    else it is already off

    U may need to have some special treatment for +- 1

    Solution