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.
721 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
3
votes
1
answer
155
views
Java: counting letters FROM A fractal algorithm shows prime number patterning
This example finds all "letter" structures.
letter a = LMLMMM
letter b = LMMMMM
letter c = MMLMMM
letter d = MMMMMM
Symbol L = live = prime candidate number
Symbol M = multiple = composite ...
5
votes
1
answer
450
views
Java: prime number envelopes FROM A fractal algorithm shows prime number patterning
It implements prime number envelopes (page 3) from my paper: https://zenodo.org/records/16829092
The full working example is on github: https://github.com/cerebrummi/primeenvelopes
"StartFA"...
10
votes
2
answers
1k
views
Java: A fractal algorithm shows prime number patterning
The fully working example finds all primes (theoretically). In real life the FA is constrained by stack size. The theoretical run is important, because it proves that all primes have a deterministic ...
7
votes
5
answers
1k
views
Prime number finder below the limit specified
Is this an optimal solution? I doubt it is. Can someone please critique my code?
...
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 ...
3
votes
1
answer
106
views
Optimizing sieving code for the Multiple Polynomial Quadratic Sieve
I wrote code for the multiple polynomial quadratic sieve (MPQS) here:
...
4
votes
2
answers
217
views
Simple Sieve of Eratosthenes
I've implemented this version of the Sieve of Eratosthenes in Rust, with inputs. I'm mostly pleased with it, but want to know if the input logic can be simplified, and if the sieve itself can be ...
2
votes
1
answer
148
views
What is the most efficient way to figure out if a single number is prime for numbers from 2 up to 2,147,483,647 in Java?
As Java programmers, we can always use the BigInteger isProbablePrime() method or store manually all prime numbers in a HashMap. This question is about the most efficient way to figure out if a single ...
6
votes
3
answers
903
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 ...
6
votes
0
answers
114
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
171
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 ai have exactly 3 divisors.
Constraints
1 <= ai <= 2.5 * 1013
In other words,
the minimum ...
8
votes
4
answers
502
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 ...
3
votes
1
answer
157
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 ...
1
vote
2
answers
141
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" ...
10
votes
1
answer
323
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 ...