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.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
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, ...
user avatar
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{...
user avatar
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 ...
user avatar
  • 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=...
user avatar
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$. ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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/...
user avatar
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 ''...
user avatar
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^{...
user avatar
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 (...
user avatar
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?
user avatar
  • 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)?...
user avatar
  • 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 ...
user avatar
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...,\...
user avatar
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$ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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? <...
user avatar
  • 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))$. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
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?
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 457