Questions tagged [primes]
The primes tag has no usage guidance.
105
questions
0
votes
2
answers
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
2
answers
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
12
votes
8
answers
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
0
answers
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
0
answers
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
0
votes
1
answer
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
6
votes
2
answers
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 ...
- 425
2
votes
1
answer
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:
...
- 199
1
vote
1
answer
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, ...
- 127
0
votes
1
answer
233
views
Four functions problem
This is not from online contest
Hi guys, a friend of mine recently give me this problem that I couldn't figure out an effective way to solve it.
Four functions
You are given four functions
$$
\begin{...
- 133
0
votes
0
answers
62
views
File compression using prime numbers
My theory
take a file examplesize:(3GB)
convert said file to a number
divide that number by a large prime number example:(2^82,589,932 · (2^82,589,933-1))[2018 Dec 07]
get the quotient and the ...
- 1
1
vote
1
answer
74
views
RSA Encryption for specitic messages x with x = ap mod pq for ap-bq=1
I want to make a following proof but I got some difficulties with it.
Would be super if you people have any tips / advises.
Introduction:
Let (N,e) be our public key and (N,s) our private key with $N=...
2
votes
0
answers
30
views
Central Trinomial Coefficients best time complexity
What is the fastest known time complexity for computing central trinomial coefficients?
Let $C_n=1,1,3,7,19,51,...$ (OEIS A002426) denote the coefficient of $x^n$ in $(x^2+x+1)^n$ starting at $n=0$.
...
- 141
1
vote
3
answers
199
views
Determine the number of elements that is divisible by a prime number in an array
I have an array (|A|≤10^6) of numbers (not guaranteed to be distinct) and a set of prime numbers.
For each of the prime numbers, I want to know how many numbers in the first array are divisible by ...
0
votes
1
answer
76
views
How efficient of this prime sieving algorithm?
I just found there is an old program of mine where I implemented the following prime sieving algorithm:
...
- 284
0
votes
1
answer
76
views
Prime factorization for compressing streams of random numbers
We covered compression/encoding/decoding of data streams very briefly last lecture and I had an odd idea:
Let's say I have a stream of random 8-Bit numbers. Now the probabilty to encounter each number ...
- 203
1
vote
1
answer
74
views
An algorithem for finding the number of primes of the form 4k+3 under some n
I was given the task to make an algorithem that can compute the number of prime's of the form 4k+3 under some n, it should be able to compute how many number's of this type are there under 10^8 (100 ...
- 33
2
votes
0
answers
58
views
Partition a set of factors so that the difference between products is minimized
I'm sure this problem must be well-known...
Given a collection $S$ of numbers, partition them into exactly two sub-collections, $A$ and $B$ (I mean, by definition $B$ is just $S-A$) such that the ...
- 279
1
vote
1
answer
65
views
While number can be checked for primality in O(n^0.5) then why was it considered to be not in P until AKS test?
While a basic algorithm to check for primality of a number 'n' [checking if a divides n for all a less than n] would take O(n), AKS test was the breakthrough after which it was placed in P complexity ...
0
votes
1
answer
39
views
Is the complement of this decision problem in $P$?
Are there any two primes that are NOT a factor of $M$ that multiply up to $M$?
Fact: Any two primes that multiply up to $M$. Must be factors of $M$!
Thus because of the fact above an $O(1)$ algorithm ...
- 57
0
votes
0
answers
31
views
Algorithm always provide a $2$_$sum$ with at least ONE prime? In polynomial-time?
Function Problem: Given $N$ find a $2$_$sum$ that uses at least $ONE$ prime.
Fact: Prime Gaps grow logarithmically on average. And, in worst case if memory serves correct it grows with a bounded ...
- 57
1
vote
2
answers
311
views
Fastest algorithm for finding the number of primes in a range
Is there an algorithm for finding the number of primes in a given range $[N, M)$ that works in time linear to $M-N$? For context, $N$ and $M$ can go up to $10^{10}$, but the distance between N and M ...
- 43
1
vote
0
answers
100
views
how did the authors of the AKS-Paper come up with the upper bound for r? and what does the multiplicative order have to do with anything?
I have been recently reading the paper "PRIMES is in P", but unfortunately a lot the steps were skipped, which led to confusion. My main problem is with the upper bound on r which was not explained at ...
- 11
0
votes
3
answers
76
views
Primality testing algorithm
Say, I would like to check a hypothesis concerning primes. Something like "there exists a prime between $n$ and $2n$ for every choice of $n$". I would like to run a code in MATLAB for choices of $n$ ...
- 440
3
votes
1
answer
134
views
Efficiently prime factorising an integer with an oracle
Suppose you have a program one_factor(N) that, given an n-digit binary number, N, returns ...
user100470
0
votes
1
answer
43
views
What computational model supports arbitrarily sized integers?
I want to do some research, but I don't think it's important the number of bits it takes to represent the integer input and arithmetic on the abstract machine. So what is the model that addresses ...
0
votes
1
answer
207
views
How much time (in hours) will it take to check if the number with 20 binary digits is the prime number?
How much time (in hours) will it take to check if the number with 20 binary digits is the prime number, in problem it's mentioned that for number with 10 digits it took 1 hour it's also said that the ...
2
votes
1
answer
117
views
Prime checking and factorization with just bit cheking
I've read about some methods of prime factorization like here and here. However, I'm wondering: what can we do in prime factorization with just some bit manipulation and without other variables/...
- 1,057
1
vote
1
answer
98
views
Is SEMIPRIME in P?
The title says it all: is there a deterministic polynomial time algorithm that tests for semiprimality? (A number $N$ is a semiprime if it is the product of two primes.) I don't understand the ''...
- 143
1
vote
2
answers
468
views
Pumping Lemma with Prime Number [closed]
$\text {Could someone please help me with this proof: }$
$L:=\left\{a^{n} d^{m} b^{k} | n, m, k \in \mathbb{N} \wedge m \text { is a prime number}\right\}$
$\text {Maybe we can say, that } w=a^{n}d^{...
- 31
3
votes
1
answer
43
views
Solve SUBSET SUM for Reciprocals of Primes
Let $p_1, ..., p_n$ distinct prime numbers with $P = \prod_{i=1}^{n}{p_i}$ and $A=(a_1, ..., a_n)$ with $a_i = P/p_i$.
Problem
Show the SUBSET SUM problem $(A, \alpha)$ can be solved in polynomial (...
- 155
0
votes
1
answer
442
views
Time complexity of Sieve of Eratosthenes [closed]
Wikipedia states that the Sieve of Eratosthenes runs in time $O(n\log\log n)$. Why is that so?
- 111
1
vote
1
answer
86
views
Is binomial(n, k)=0 (mod n) when gcd(n, k)=1? When gcd(n, k)>1?
I was programming the AKS primality test, and I have two questions.
Is it correct that if gcd(n, k)=1, then binomial(n, k)=0 (mod n)?
Is it correct that if gcd(n, k)>1, then binomial(n, k)>0 (mod n)?...
- 11
0
votes
0
answers
158
views
Is the Time Complexity of Trial Division Exponential? [duplicate]
I know that there is already a similar question asked on here, but after reading the wiki page on trial division, I am confused, and the other answer doesn't help. The wiki page states that when doing ...
1
vote
1
answer
182
views
What is the complexity of this prime trial division algorithms?
I have two algorithms. What are their time complexities?
The first algorithm checks the modulo of all odd integers from $3,5,...\sqrt{n}$.
The second algorithm generates a list of prime from $2,3...,\...
- 11
0
votes
1
answer
42
views
Coprimes satisfying a pair
We know that number of coprimes less than a number can be found using Euler's totient function.
But if there are two numbers $p$ and $q$ and we need to find number of numbers less than $q$ ...
- 364
2
votes
0
answers
262
views
Min no.of operations required to convert an array to which it should contain elements of equal frequency
I have come across this tricky problem. An array of N elements should be converted to another array within k operations such ...
- 125
2
votes
1
answer
440
views
Complexity of brute force primality test in the number of digits
I'm wondering how to express the complexity of a brute force primality testing algorithm in the number of digits the number under test has. The brute force algorithm just checks whether $n$ is prime ...
- 187
2
votes
1
answer
196
views
Listing all prime numbers less than an integer N
I am trying to solve this problem listing all prime numbers less than an integer but using the smallest amount of memory.
Is it possible to solve this problem using a smaller amount of memory?
<...
- 35
1
vote
2
answers
319
views
Randomly Choosing a N-Bit Prime
I've been studying some number theory, and I came across this problem:
Lagrange’s prime number theorem states that as N increases, the number of primes less than $N$ is $Θ(N/ log(N))$.
...
- 163
1
vote
1
answer
139
views
The time complexity of the Wikipedia version of Pollards $(p-1)$ algorithm
I am trying to understand the runtime of Pollard's $(p-1)$-algorithm as presented on Wikipedia. There the author writes that it takes $\mathcal{O}(B\log B\log^2n)$ time, but I do not see why.
Here ...
- 423
1
vote
3
answers
197
views
Determining number of elements divisible by at least one prime of set
I have an array ($|A|\leq 10^6$) of numbers ($A_i\leq10^6$) and a set of prime numbers. I have to find the count of the elements in the array that are divisible by at least one of the numbers in the ...
- 11
2
votes
2
answers
277
views
Logarithmic run time for calculating prime numbers?
Here's the function I'm currently analyzing. I know it's not the most optimal but I'm not understanding the $\theta()$ of this algorithm. I've been told that it's not actually $\theta(n)$ but instead ...
- 23
4
votes
1
answer
2k
views
Why is the complexity of factorial a function of n?
When we compute the complexity of calculating factorial of a number $n$ why is it in terms of $n$ instead of the number of the number of bits occupied by the number of bits occupied by $n$ (like we do ...
- 225
0
votes
2
answers
205
views
Is finding all primes less than n, doable in polynomial time?
Bear in mind I'm almost a complete noob at complexity theory.
I was reading about how AKS Primality shows that numbers of size n can be shown to be prime or composite in polynomial time. Given that, ...
- 101
8
votes
3
answers
5k
views
Algorithm for checking if a list of integers is pairwise coprime
Are thre any efficient algorithms for checking if a list of integers is pairwise coprime, or would a more general algorithm be the best option available?
- 183
3
votes
2
answers
218
views
Dijkstra's Notes on Structured Programming - concerning the program to compute first 1000 prime numbers
In his "Notes on Structured Programming" essay, E. W. Dijkstra gives an example of a program that computes the first 1000 primes (Section 9. "A First Example of Step-Wise Program Composition").
The ...
1
vote
1
answer
37
views
Show a sequence of distinct Primes number is O(log n)
Suppose I have a sequence:
$$n = \prod_{i=1}^{r(n)} p_i^{d_i}$$
for some primes $p_1 < p_2 < \dots < p_{r(n)}$, and each $d_i \geq 1$ an integer. The function $r(n)$ denotes the number of ...
- 13
1
vote
4
answers
711
views
What is the big-$\Omega$ complexity of Fermat's Little Theorem?
Fermat's Little Theorem states that if an integer $n$ is prime them
$$
a^n \equiv a \pmod n \hspace{10mm} (*)
$$
for any $a \in \mathbb{N}$
My question is, is it correct to say that testing $(*)$ for ...
- 457
2
votes
2
answers
162
views
What is the complexity of checking whether an integer $n \geq 2$ is expressible in the form $a^b$ where $a, b \in \mathbb{N}$?
I am currently studying the paper Primes is in P and have a question regarding 5 section of this paper. Line 1 of the algorithm (on page 3) requires the following operation to be performed
...
- 457