Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Questions tagged [primes]

The tag has no usage guidance.

105 questions
Filter by
Sorted by
Tagged with
58 views

### Integer/prime factorization to 3 SAT

So essentially as the title says, I just want to understand how its done. I have a light idea from my own research, but its failing at one point, and I feel it maybe due to crucial point missing in my ...
1 vote
47 views

### $L_p$ contains all binary strings whose value as binary number is prime. What are those values?

Context-: https://math.stackexchange.com/questions/1600257/determining-if-a-binary-string-represents-a-prime-integer Confused text-: The problem of testing primality can be expressed by the language ...
• 51
2k views

### Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?

I wish there were more, but the subject pretty much captures my whole question. Is there a non-Turing-complete model (some constrained term rewriting system or automaton or what have you) which is ...
• 254
1 vote
52 views

### Find array of coprime integers whose average is maximized

I am creating a class to store large integers in a residue number system. I want each "integer" to be 4-12GB in size and be comprised of 64-bit moduli. These moduli must be pairwise coprime ...
1 vote
25 views

### Postponed sieve algorithm with start logic [closed]

Based on the answer by Will Ness, I've been using a JavaScript adaptation for the postponed sieve algorithm: ...
• 111
54 views

### How to get the numbers in the Sieve of Eratosthenes with wheel factorisation?

I'd like some help with figuring out the algorithm for the Sieve of Eratosthenes with wheel factorisation. Specifically, I need help figuring out if it's possible to convert between an index and the ...
• 111
921 views

### How can we count the number of pairs of coprime integers in an array of integers? (CSES)

For reference, I am trying to solve this CSES Problem. The problem basically states that given up to $10^5$ positive integers in the range $[1, 10^6]$, find the number of pairs of those positive ...
24 views

### How to approximate big composite number factors?

There is a big 1024-bits number A that was obtained by multiplying two numbers B and C.Are there any ways to get first numerical digits of these numbers? How example: ...
1 vote
48 views

### Is it true that PRIMES are in SPARSE?

I'm wondering if PRIMES, the language of all prime numbers represented in binary, which is $\{10, 11, 101, 111, 1011, 1101, ...\}$, belongs to the SPARSE class, a set of all sparse languages, that is, ...
233 views

• 457