All Questions
25 questions
14
votes
4
answers
2k
views
Codechef: Prime Number Generator
Peter wants to generate some prime numbers for his cryptosystem. Help
him! Your task is to generate all prime numbers between two given
numbers!
Input
The input begins with the number t of test cases ...
- 241
14
votes
3
answers
8k
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:
...
- 263
12
votes
3
answers
5k
views
Python π = 1 + (1/2) + (1/3) + (1/4) - (1/5) + (1/6) + (1/7) + (1/8) + (1/9) - (1/10) ...1748 Euler
I wrote this code to show that my reddit post is correct.
After the first two terms, the signs are determined as follows: If the denominator is a prime of the form 4m − 1, the sign is positive; if ...
- 643
12
votes
1
answer
1k
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,176
9
votes
6
answers
4k
views
Goldbach’s Conjecture in Python
Input Format
Input starts with an integer n (1 ≤ n ≤ 100) indicating the number of cases. The following n lines each contain a test case of a single even number x (4 ≤ x ≤ 32000).
Output Format
For ...
8
votes
1
answer
3k
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 ...
7
votes
2
answers
913
views
Counting Fermat witnesses and liars
We were asked to implement a program that calculates the number of Fermat witnesses and liars for odd numbers greater 1. This involves Fermat’s little theorem.
Fermat’s little is used to identify ...
- 3,701
7
votes
4
answers
1k
views
6
votes
2
answers
630
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, <...
user1174209
6
votes
2
answers
104
views
Finding consecutive primes matching p, p + 4, p + 6, p + 10, p + 12, p + 16
Someone asked about this question on the main StackOverflow. The full question is:
Given a value N, find p such that all of ...
- 161
6
votes
1
answer
921
views
Decompose any number to its prime factors raised to their respective powers
A simple code which takes the given number as input and gives all of its prime factors raised to their respective powers. It works well up to 10⁶; after that it slows down greatly for some numbers. ...
- 281
5
votes
4
answers
7k
views
Generating a list of primes of a given length
After considerable effort, I've come up with the following code to generate a list of primes of a given length.
I would be very interested to see how an experienced coder would modify my code to make ...
Matt
5
votes
2
answers
1k
views
Prime Number Generator (6n + 1 or 6n - 1)
This generator is like most where it brute forces an integer: it see whether the integer is divisible by any of the primes; if so, then it's not a prime and vice versa. This though only compares ...
- 845
5
votes
1
answer
911
views
Number of divisors of a factorial
I was solving the DIVFACT problem from Sphere Online Judge:
Given a number, find the total number of divisors of the factorial of the number.
Since the answer can be very large, print the answer ...
- 153
5
votes
1
answer
1k
views
Sieve of Atkin in Python
I recently implemented the Sieve of Atkin prime generating algorithm in Python. Though I know the term "pythonic" isn't exactly set in stone, I can tell that my program doesn't quite take advantage of ...
- 171