AlirezaBest's blog

Whats the most optimal way to detect prime numbers from 2 to n?
By AlirezaBest, history, 7 months ago, In English

Hello..I was solving problems of cf round 1083 Div.2 and when i encountered problem B i was fighting with time limit error i used the famous O(sqrt(n)) algorithm to detect prime numbers..but is there an algorithm from better order or not?

Thank you for reading:)

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
7 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Learn sieve of Eratosthenes. It can detect primes till N in O(N log(log(N))

→ Reply
»
7 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

The problem has very high n (n <= 1e9), then precomputing the primes (sieve approach) will not work due to memory limit.

I think its very probable that your algorithm may not be O(sqrt(n)), I used a very simple approach on the same problem and got AC.

You can refer to this article on cpalgorithms for prime factorization: https://cp-algorithms.com/algebra/factorization.html.

→ Reply
»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

you need to learn prime factorization for solving that problem

https://cp-algorithms.com/algebra/factorization.html

→ Reply
»
7 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

You probably did something inefficient in your code. I solved it in O(sqrt n) and got AC. Since (sqrt 10e9 *100 ~ 3e7+)

Personally, I know two optimization approaches that I usually use:

1.Keep dividing by a factor while it divides the number, and also you can skip even numbers after checking 2.

2.Precompute primes up to sqrt[n] (for sqrt(1e9) only 3e3+ primes) and iterate over them directly.

→ Reply
»
7 months ago, hide # |
← Rev. 5  
Vote: I like it 0 Vote: I do not like it

you can use this function 

vector < int64_t > pdivs_ ( int64_t N ) {
  vector < int64_t > P ;
  for ( int64_t i = 2; i * i <= N ; i ++ ) {
    if ( N % i == 0 ) {
      P.push_back ( i ) ;
      while ( N % i == 0 ) 
          N /= i ;
    }
  }
  if ( N > 1 ) P.push_back ( N ) ;
  return P ;
}

to get the list of prime factors of a number N in cpp, since i had written this function before i managed to solve B in 3 minutes

but for your question getting prime numbers from 1 to N you can use a sieve

vector < int64_t > _Sieve ( int64_t N ) { 
  vector < int64_t > spf ( N + 1 , 0 ) ;  
  vector < int64_t > pr ;
  for ( int64_t i = 2 ; i <= N ; i++ ) {
    if ( spf [ i ] == 0) {       
      spf [ i ] = i ;
      pr.push_back ( i ) ;
    }
    for ( int64_t p : pr ) {
      if ( p > spf [ i ] || i * p > N ) break;
      spf [ i * p ] = p ;
    }
  }
  return pr ;
}

this will give you the list of primes from 1 to N in O ( N ) time complexity but for 2205B - Simons and Cakes for Success you need to use the pdivs function to get prime divisors of a number

→ Reply