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.
722 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
9
votes
4
answers
799
views
Find the smallest semiprime satisfying a bunch of conditions
The purpose of this code is to find the smallest semiprime \$s = a b\$ satisfying a bunch of conditions stated in the Math.SE question What is the smallest "prime" semiprime?. The conditions ...
3
votes
1
answer
177
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
468
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
2k
views
Prime number finder below the limit specified
Is this an optimal solution? I doubt it is. Can someone please critique my code?
...
11
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
115
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
240
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
183
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
922
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
124
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
192
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
522
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
173
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
158
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" ...