# primes's questions - English 1answer

62 primes questions.

### 2 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 ...

### 3 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 ...

### Is finding all primes less than n, doable in polynomial time?

2 answers, 44 views complexity-theory np primes
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, ...

### 8 Algorithm for checking if a list of integers is pairwise coprime

3 answers, 763 views algorithms primes
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?

### 3 Dijkstra's Notes on Structured Programming - concerning the program to compute first 1000 prime numbers

2 answers, 123 views algorithms algorithm-analysis primes
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 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 ...

### 1 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 ...

### 1 Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test?

2 answers, 97 views complexity-theory primes
In the paper "PRIMES is in P" the following is said (page 1): Let PRIMES denote the set of all prime numbers. The definition of prime numbers already gives a way of determining if a number $n$ is ...

### -1 developing a Turing Machine that checks for powers of 2

2 answers, 1.232 views algorithms turing-machines primes
I want to write a Turing machine which checks for unary powers of 2 but without the use 0s, only accepting as input a series of 1s and dashes. I do not know of a sequence of states which would allow ...

### 4 How to compute all primes between upto $n$ in time $O(n)$ time?

1 answers, 142 views algorithms enumeration primes
Suppose that I want to compute all the prime numbers between 2 and $n$. The natural way or most obvious way to do so is given below. Let $A$ is an array contain the numbers from $1$ to $n$. For $j=2$ ...

### 2 Time complexity of finding an integer between $x$ and $2x$

1 answers, 48 views algorithms primes
Consider receiving as input $x\in\mathbb N$ and computing some (any) prime $p\in[x,2x]$. What is the complexity of the above problem? A natural way to approach this problem is to generate random ...

### 1 What should I do if I think I wrote an algorithm that is _generally_ faster than Atkin Sieve? [closed]

1 answers, 77 views algorithms primes
I've been having some fun with prime numbers. A few months ago I sat down to see if I could write something that could compete with Atkin Sieve and ended up with an algorithm that, on my local tests ...

### 9 Why Miller–Rabin instead of Fermat primality test?

3 answers, 3.662 views algorithms primes
From the proof of Miller-Rabin, if a number passes the Fermat primality test, it must also pass the Miller-Rabin test with the same base $a$ (a variable in the proof). And the computation complexity ...

### 1 Is Mersenne primality testing necessarily EXPTIME?

The computational complexity of primality testing is usually specified in relation to the bit length of the number being tested. However, Mersenne numbers have the special property that the ...

### 20 Data compression using prime numbers

5 answers, 4.791 views information-theory data-compression primes
I have recently stumbled upon the following interesting article which claims to efficiently compress random data sets by always more than 50%, regardless of the type and format of the data. Basically ...

### 1 Is this a Fruitful Primality Testing scheme?

1 answers, 102 views algorithms algorithm-analysis primes
Today I had an insight into an alternative deterministic algorithm for testing the primality of a number. I want to know if this algorithm is useful, and worth pursuing. I'll describe the idea behind ...

### 8 More details about the Baillie–PSW test

3 answers, 262 views reference-request number-theory primes
It's clear that Mathematica uses the Baillie–PSW test for its PrimeQ function (which tests primality), and as I read in the Mathematica documentation, it starts with trial division, then base 2 ...

### 1 Algorithm which finds the maxmal solution that satisfies the following constraints

I have $a_1, a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$ and an upper bound $U$ and $n$ linear equations of the form: $k_1 * a_1 + b_1 = x$ $k_2 * a_2 + b_2 = x$ $\dots$ $k_n * a_n + b_n = x$ ...

### 2 AKS primality test- Lemma 4.3, not following

0 answers, 33 views complexity-theory cryptography primes
I'm reading the AKS primality test paper as it is found here. I'm confused about a statement in Lemma 4.3: "Note that $(r, n)$ cannot be divisible by all the prime divisors of $r$ since otherwise $r$...

### Why some state that Primes is in NP? [duplicate]

0 answers, 31 views complexity-theory primes
Why some books state that Primes is a NP problem if, as a decidibility problem, it can be solved in polynomial time? A simple example: A number can has its primality tested by dividing it by all ...

### 1 minimize sum of primes with a lower bound on product

I can't quite figure out an algorithm for this: Given some integer n, what subset of the primes (so no repeats) would yield the lowest possible sum if their product is at least n? Example: 6 -> 2*3, ...

### Design a Turing Machine Checking if power is prime

0 answers, 360 views turing-machines primes
I have to design a Turing Machine to do the following, but I don't really know where to start with this question. Any help would be very much appreciated. I should design a Turing Machine accepting ...

### Given a prime power, is it possible to efficiently compute the prime

1 answers, 71 views algorithms primes
Suppose that I am given as input the number $p^i$ for some prime $p$ and some positive integer $i$. I wish to find $p$ and $i$. Is there an algorithm to do this that works in time polynomial in the ...

### 10 Efficiently computing the smallest integer with n divisors

2 answers, 214 views number-theory primes
In order to tackle this problem I first observed that $$\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1)$$ Where $\phi(m)$ is the number of (not ...

### 1 Hash function to hash 6-digit positive integers

Let UID denote a unique identifier. UID's are represented as 6-digit positive integers. I want to insert a collection of UID's in a hash table with $M$ buckets, where $M$ is a prime number (for ...

### 1 Modifications to speed up the AKS primality proving

1 answers, 80 views reference-request number-theory primes
It is clear that AKS primality proving is the newest one, but as the results show it is not the fastest one. When I try the 9 digits long prime number it consume about 6 minutes to give you the ...

### 1 Average runtime of naive primality test

1 answers, 109 views number-theory primes
The naive prime test goes something like this:is_prime(n): for(i=2; i<=sqrt(n); ++i): if n mod i == 0 : return false return trueIf $n$ is ...

### 3 What is the fastest to find just smallest prime number to a given number N where N can be as large as 10^18?

3 answers, 266 views algorithms primes
During a programming contest I was asked to find just smallest prime number to given number N. As Sieve cannot be used and brute force also doesn't work. So, I was wondering is there any other faster ...

### 2 Finding coprimes closest to a certain target

2 answers, 215 views algorithms primes
Given an input $m$, I am trying to find an algorithm that will give me the number $p$ that is closest to $\tfrac47 m$ and co-prime with $m$. Where $m$ is odd, I have no problem producing an outcome ...

### 5 Express a number as a sum of consecutive primes (How many ways?)

2 answers, 514 views algorithms primes