Skip to main content
Code Review

Return to Answer

replaced http://codereview.stackexchange.com/ with https://codereview.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

Few additional thoughts to Fast Number Factorization in PythonFast Number Factorization in Python answer.

is_prime()

In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.

prime_factors()

There is one thing you miss in your code. Lets take prime number, let is be \$ 10007 \$ and multiply it by \$ 2 \$, we will receive \$ 20014 \$. Its factorization will be \$ 20014 = 10007 \times 2 \$.

Now lets analyze your prime_factors. You will find that \$ 2 \$ is prime divisor of \$ 20014 \$ and will continue to iterate through all prime numbers up to \$ 10007 \$ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal \$ 1 \$ than it is prime.

This trick can reduce time for such cases.

As the result, you can assume that you need to generate sieve up to square root of highest number.

Few additional thoughts to Fast Number Factorization in Python answer.

is_prime()

In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.

prime_factors()

There is one thing you miss in your code. Lets take prime number, let is be \$ 10007 \$ and multiply it by \$ 2 \$, we will receive \$ 20014 \$. Its factorization will be \$ 20014 = 10007 \times 2 \$.

Now lets analyze your prime_factors. You will find that \$ 2 \$ is prime divisor of \$ 20014 \$ and will continue to iterate through all prime numbers up to \$ 10007 \$ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal \$ 1 \$ than it is prime.

This trick can reduce time for such cases.

As the result, you can assume that you need to generate sieve up to square root of highest number.

Few additional thoughts to Fast Number Factorization in Python answer.

is_prime()

In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.

prime_factors()

There is one thing you miss in your code. Lets take prime number, let is be \$ 10007 \$ and multiply it by \$ 2 \$, we will receive \$ 20014 \$. Its factorization will be \$ 20014 = 10007 \times 2 \$.

Now lets analyze your prime_factors. You will find that \$ 2 \$ is prime divisor of \$ 20014 \$ and will continue to iterate through all prime numbers up to \$ 10007 \$ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal \$ 1 \$ than it is prime.

This trick can reduce time for such cases.

As the result, you can assume that you need to generate sieve up to square root of highest number.

added 1 character in body
Source Link
outoftime
outoftime
  • 1.8k
  • 10
  • 18

Few additional thoughtthoughts to Fast Number Factorization in Python answer.

is_prime()

In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.

prime_factors()

There is one thing you miss in your code. Lets take prime number, let is be \$ 10007 \$ and multiply it by \$ 2 \$, we will receive \$ 20014 \$. Its factorization will be \$ 20014 = 10007 \times 2 \$.

Now lets analyze your prime_factors. You will find that \$ 2 \$ is prime divisor of \$ 20014 \$ and will continue to iterate through all prime numbers up to \$ 10007 \$ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal \$ 1 \$ than it is prime.

This trick can reduce time for such cases.

As the result, you can assume that you need to generate sieve up to square root of highest number.

Few additional thought to Fast Number Factorization in Python answer.

is_prime()

In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.

prime_factors()

There is one thing you miss in your code. Lets take prime number, let is be \$ 10007 \$ and multiply it by \$ 2 \$, we will receive \$ 20014 \$. Its factorization will be \$ 20014 = 10007 \times 2 \$.

Now lets analyze your prime_factors. You will find that \$ 2 \$ is prime divisor of \$ 20014 \$ and will continue to iterate through all prime numbers up to \$ 10007 \$ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal \$ 1 \$ than it is prime.

This trick can reduce time for such cases.

As the result, you can assume that you need to generate sieve up to square root of highest number.

Few additional thoughts to Fast Number Factorization in Python answer.

is_prime()

In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.

prime_factors()

There is one thing you miss in your code. Lets take prime number, let is be \$ 10007 \$ and multiply it by \$ 2 \$, we will receive \$ 20014 \$. Its factorization will be \$ 20014 = 10007 \times 2 \$.

Now lets analyze your prime_factors. You will find that \$ 2 \$ is prime divisor of \$ 20014 \$ and will continue to iterate through all prime numbers up to \$ 10007 \$ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal \$ 1 \$ than it is prime.

This trick can reduce time for such cases.

As the result, you can assume that you need to generate sieve up to square root of highest number.

Source Link
outoftime
outoftime
  • 1.8k
  • 10
  • 18

Few additional thought to Fast Number Factorization in Python answer.

is_prime()

In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.

prime_factors()

There is one thing you miss in your code. Lets take prime number, let is be \$ 10007 \$ and multiply it by \$ 2 \$, we will receive \$ 20014 \$. Its factorization will be \$ 20014 = 10007 \times 2 \$.

Now lets analyze your prime_factors. You will find that \$ 2 \$ is prime divisor of \$ 20014 \$ and will continue to iterate through all prime numbers up to \$ 10007 \$ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal \$ 1 \$ than it is prime.

This trick can reduce time for such cases.

As the result, you can assume that you need to generate sieve up to square root of highest number.