1
vote
1answer
47 views

Speeding up prime factorization

I have written the following code for returning the list of prime factors. Any speed-enhancing suggestions? ...
2
votes
1answer
42 views

Custom module of common functions

I got sick and tired of writing certain functions over and over again, so I made a module that has those functions whenever I need them. I don't use it for code I plan on sharing, so I don't need to ...
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
99 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
67 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
378 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. ...
3
votes
1answer
104 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
306 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
885 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
174 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
967 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
108 views

Strange performance difference

For exercise, I wrote this code: ...
4
votes
1answer
163 views

Sum of primes program is taking too long

I don't understand what is taking the program so long: ...
5
votes
3answers
613 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
241 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
77 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
58 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
147 views

Prime number dictionary

I attempted to write a read-only dictionary, containing primes: ...
3
votes
2answers
113 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
104 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 ...
1
vote
2answers
269 views

Efficient way of code reuse for finding the largest prime factor

I was doing timing with variations of function largest_prime_factor. I was able to write a better one largest_prime_factor2. ...
4
votes
4answers
726 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
645 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 ...
4
votes
3answers
794 views

Calculating all prime palindromes from 0 to 1000 and printing the largest

I have often read about how important clear and efficient code is. Also often people talk and write about 'beautiful' code. Some hints and critic from experienced developers for the following code ...
8
votes
1answer
461 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
490 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
185 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
155 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
658 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
99 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
2k 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
144 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 ...
4
votes
2answers
285 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
185 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 ...
5
votes
2answers
418 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
288 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 ...