Questions tagged [primes]
Primes or prime numbers are numbers which are divisible only by themselves and one, starting with 2, 3, 5, 7, 11.... They are commonly used in encryption and hashing algorithms.
717
questions
5
votes
3
answers
855
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 ...
- 53
5
votes
0
answers
83
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
134
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 ...
6
votes
4
answers
437
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 ...
- 67
3
votes
1
answer
132
views
Miller-Rabin implementation is very slow
I implemented the Miller-Rabin-Primetest in python3. But I have the feeling it is very slow. I know that there are faster version in gmpy2 package, but I want to compare it with another code I have in ...
- 141
1
vote
2
answers
123
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
9
votes
1
answer
292
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 ...
- 193
6
votes
2
answers
1k
views
C code for finding prime numbers
I have created a program to find prime numbers up to the 32nd power of 2. It uses the sieve of Eratosthenes. I would appreciate it if you could let me know any bugs or improvements I can make.
...
- 180
1
vote
1
answer
102
views
Project Euler 10(Python) | Summation of Primes
This is my Python3 code which solved the 10th problem of Project Euler. I haven't passed the last 2 time limit test cases.
...
- 67
3
votes
1
answer
274
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 ...
- 67
3
votes
1
answer
70
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 ...
- 77.3k
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
720
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
146
views
Hunting for the 100,001st prime in Rust
Most of my programming experience is in Python, but my first language was C, and I was intrigued by the combination which Rust offers: a streamlined syntax and no manual memory management, but with ...
- 441
2
votes
2
answers
133
views
generate prime factors via wheel factorization
I want to factor random values of n that range from uint.MinValue to uint.MaxValue as ...
- 1,940