All Questions
Tagged with performance primes
215 questions
10
votes
3
answers
1k
views
Computing π(x): the combinatorial method
This is my C++ implementation of Computing π(x): the combinatorial method by Tomás Oliveira e Silva. The math involved is elementary number theory, but fiddly and not the focus here. I have ...
- 1,201
3
votes
1
answer
93
views
Optimizing sieving code for the Multiple Polynomial Quadratic Sieve
I wrote code for the multiple polynomial quadratic sieve (MPQS) here:
...
- 186
6
votes
3
answers
882
views
Project Euler 127 - abc-hits
Problem (Rephrased from here):
The radical of \$n\$, \$rad(n)\$, is the product of distinct prime factors of \$n\$. For example, \$504 = 2^3 × 3^2 × 7\$, so \$rad(504) = 2 × 3 × 7 = 42\$.
We shall ...
- 63
6
votes
0
answers
104
views
Optimizing SymPy Implementation of prime factorization in form of QUBO
I'm trying to reproduce a paper on Prime Factorization. This paper converts the problem into a QUBO form, which then we can map it to an Ising Minimizer. I've basically done everything and I've ...
2
votes
1
answer
145
views
Count how many numbers in a range have exactly three divisors
The challenge
Given array a of n numbers, I need to count how many positive numbers less than each aᵢ have exactly 3 divisors.
Constraints
1 <= aᵢ <= 2.5 * 10¹³
In other words,
the minimum ...
8
votes
4
answers
483
views
Optimal Solution for the Four Divisors Problem on LeetCode
I recently encountered the Four Divisors problem on LeetCode and managed to achieve a 100% beat rate with my solution. I'd like to share it with you all and gather feedback on its effectiveness and ...
- 107
1
vote
2
answers
131
views
Miller-Rabin prime test
I have an implementation of the Miller-Rabin prime test, coded in Python 3.
I want to use that as a comparison to a prime test which I coded myself.
Unfortunately I have no idea how "fast" ...
- 141
10
votes
1
answer
311
views
Construct a performant sieve of Atkin in Rust
I have implemented the sieve of Atkin in Rust. It can find all primes till 1,000,000,000 in 4.5 s using 34.4 MiB on my 1.4 GHz machine. This is a direct implementation (with some optimisations made ...
- 203
3
votes
1
answer
335
views
Project Euler 60: Prime Pair Sets
Project Euler Prime Pair Sets:
The primes 3, 7, 109, and 673 are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime.
For example, taking 7 ...
- 77
3
votes
1
answer
82
views
Find perfect and amicable numbers
I've been playing with perfect, amicable and social numbers lately, and created a class for investigating these. At present, it has functions to return the perfect and amicable numbers in a specified ...
- 84.9k
4
votes
2
answers
1k
views
Miller-Rabin Primality Test in Python
I have the following implementation of the Miller-Rabin test in Python:
...
- 41
4
votes
2
answers
736
views
Performance of Haskell prime sieve
I have this code, which is a pseudo-Sieve of Eratosthenes for generating primes:
...
- 173
3
votes
1
answer
221
views
Find factor pairs of an integer in Rust
I'm trying to efficiently generate all pairs of factors of a number n.
For example, when n=27, the factor pairs are (1, 27), (3, 9), (9, 3), (27, 1)
The order in which the pairs are found is not ...
- 93
4
votes
1
answer
564
views
Prime factorization algorithm by using the multiprocessing module of Python
I may introduce a Python code of prime factorization which is from my personal project that I'm working on.
...
- 59
1
vote
1
answer
141
views
Numpy segmented Sieve Of Eratosthenes
For the segmented Sieve Of Eratosthenes, I have devised the following code provided. And I understand that it is not the best implementation; However, it should be much quicker than what it is now. ...
- 55