Tagged Questions
9
votes
4answers
2k views
Is prime check in Python: can this be more pythonic?
I have the following function that checks if a number is prime:
...
10
votes
1answer
93 views
Sieve of Atkins algorithm
I got the inspiration to write this algorithm from this question. The OP cited the Sieve of Atkin as one of the fastest ways to generate primes. So I figured I would give it a try:
...
4
votes
1answer
65 views
Checking for Prime Numbers [closed]
def is_prime(n):
if n % 2 == 0 and n > 2:
return False
return all(n % i for i in xrange(3, int(math.sqrt(n)) + 1, 2))
The code works fine for a ...
5
votes
1answer
361 views
Sieve of Eratosthenes - Standard and Optimized implementation
I am a Java developer who is taking Python for the first time.
I'm sure this is not at all elegant since I am thinking more in C syntax.
...
2
votes
1answer
64 views
Project Euler 27 - Quadratic Primes
Project Euler problem 27
I decided to try simple brute force, and it worked surprisingly quickly. How can this be optimized?
...
3
votes
2answers
192 views
Prime generator program SPOJ time limit exceed
Problem Statement
Input
The input begins with the number t of test cases in a single line
(t<=10). In each of the next t lines there are two numbers m and n (1
<= m <= n <= ...
17
votes
5answers
852 views
Count distinct primes, discarding palindromes, in under 2 seconds
Problem Statement
Generate as many distinct primes P such that reverse (P) is also prime
and is not equal to P.
Output:
Print per line one integer( ≤ 1015 ). Don't print more than
...
11
votes
1answer
149 views
Tonelli-Shanks algorithm implementation of prime modular square root
I did an implementation of the Tonelli-Shanks algorithm as defined on Wikipedia. I put it here for review and sharing purpose.
Legendre Symbol implementation:
...
5
votes
4answers
830 views
Sieve of Eratosthenes - Python
I've been doing a lot of Project Euler lately and just wanted to make sure my implementation was as good as it could be. Does anyone have any suggestions on speed this up?
...
7
votes
1answer
107 views
4
votes
1answer
148 views
5
votes
3answers
557 views
Summation of primes takes forever
Project Euler Problem 10 asks: "What is the sum of all prime numbers below 2 million?"
How do I speed up my code? It's taking forever and I have never gotten the answer. However, I am sure that my ...
3
votes
3answers
229 views
How Pythonic is my Project Euler #5? (LCM of [1, 2, …, 20])
I have implemented a solution to Project Euler problem 5:
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive ...
0
votes
1answer
72 views
Review my prime factorization function. Is it complete?
This is a function designed to return all the prime factors of a given number, in sorted order from least to greatest, in a list. It relies on another function that checks if a given number is prime. ...
3
votes
1answer
57 views
Any problems with this prime checker script?
I have just made what seems to me to be the first reliable prime-checking program that works. However, I am not sure if it is completely reliable, or if there are problems. It relies on list-making ...
3
votes
1answer
141 views
3
votes
2answers
108 views
Attempting to efficiently compute the largest prime factor
As per the help, here's what I'm looking for from this post: best practice and practical advice about (what I think is describable as) buffering the output of a function.
So I'm working on the third ...
0
votes
2answers
2k views
Problem in calculating prime numbers in python [closed]
I'm a noob in programming. I was asked to code a program that can calculate prime numbers. So i coded as provided below. But it prints all the Odd Numbers instead of Prime Numbers. I think the Value ...
4
votes
1answer
101 views
User-input prime number generator
What do you consider the readability of this program?
Do you think it's easy to understand what the variables and functions do just by reading their names?
Would you prefer more, less, or this amount ...
4
votes
4answers
644 views
better code for generating primes
After considerable effort, I've come up with the following code to generate a list of primes of given length.
I would be very interested to see how an experienced coder would modify my code to make it ...
7
votes
1answer
614 views
Project Euler 407: Is there any more optimal way to solve this idempotent equation (modulo n ring)?
Project Euler problem 407:
If we calculate a2 mod 6 for 0 ≤ a ≤ 5 we get: 0, 1, 4, 3, 4, 1.
The largest value of a such that a2 mod 6 = a is 4.
Let's call M(n) the largest value of a < n ...
8
votes
1answer
429 views
Project Euler #3 - how inefficient is my code?
So I am essentially a complete newbie to programming, and have been attempting to learn Python by completing the Project Euler problems. I haven't gotten very far, and this is my code for problem #3 :
...
1
vote
2answers
424 views
Returning a list of divisors for a number
This function takes in a number and returns all divisors for that number. list_to_number() is a function used to retrieve a list of prime numbers up to a limit, ...
2
votes
2answers
183 views
Criticize my first Python module please
This is a Python module I have just finished writing which I plan to use at project Euler. Please let me know how I have done and what I could do to improve it.
...
4
votes
1answer
148 views
Largest Prime Factor
I'm trying to learn Python by working my way through problems on the Project Euler website. I managed to solve problem #3, which is
What is the largest prime factor of the number 600851475143 ?
...
5
votes
4answers
624 views
Any better way to solve Project Euler Problem #5?
Here's my attempt at Project Euler Problem #5, which is looking quite clumsy when seen the first time. Is there any better way to solve this? Or any built-in library that already does some part of the ...
2
votes
1answer
98 views
Code review needed for my Prime factorization code
Below is the code for knowing all the prime factors of a number. I think there must be some better way of doing the same thing. Also, please tell me if there are some flaws in my code.
...
1
vote
2answers
1k views
Functional prime factor generator
I have this prime factor generator for some number n. It returns list of all prime factors. In other words, product of the list equals ...
3
votes
3answers
141 views
Naive prime finder, unexpected behavior in Python
I have verified that both of my following functions successfully find prime numbers. I was pretty sure the function called is_prime_new would be faster than ...
8
votes
1answer
174 views
4
votes
2answers
284 views
Improving runtime of prime generation
I just answered the question on project euler about finding circular primes below 1 million using python. My solution is below. I was able to reduce the running time of the solution from 9 seconds to ...
5
votes
3answers
7k views
Prime factorization of a number
I'm trying to learn Python through the excellent online book Dive Into Python 3. I have just finished chapter 2 about data types and felt like trying to write a program on my own.
The program takes ...
2
votes
1answer
176 views
Why is one prime number function hugely faster than another? [closed]
I've found this excellent prime number module file from here as I work through the Project Euler problems, and I'm trying to fully understand the code and the maths behind it.
I've come to a hitch on ...
4
votes
2answers
408 views
Euler 35 - python solution taking too long
Here is my solution for Project Euler 35. (Find the number of circular primes below 1,000,000. Circular meaning all rotations of the digits are prime, i.e. 197, ...
1
vote
4answers
1k views
Sieve of Eratosthenes: making it quicker
I was thinking about doing problem 23 of Project Euler. It includes the difficulty where you have to factorize primes. I had already done that in problems I solved earlier, but it was only necessary ...
3
votes
2answers
282 views
Optimizing this 'print up to the nth prime number' script
I've been seeking to optimize this algorithm, perhaps by eliminating one of the loops, or with a better test to check for prime numbers.
I'm trying to calculate and display 100000 prime numbers has ...
