# Questions tagged [primes]

The tag has no usage guidance.

86 questions
Filter by
Sorted by
Tagged with
26 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 ...
28 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 ...
76 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 ...
91 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 ...
45 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$ ...
63 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 ...
35 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 ...
67 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 ...
49 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/...
62 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 ''...
63 views

33 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$ ...
158 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 ...
214 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 ...
92 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? <...
205 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))$. ...
76 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 ...
79 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 ...
142 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 ...
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 ...
159 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, ...
4k 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?
186 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 ...
35 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 ...
435 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 ...
135 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 ...
473 views

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

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 ...
162 views

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

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$ ...
50 views

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

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 ...
94 views

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

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 ...
126 views

### 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 ...
110 views

### Is this a Fruitful Primality Testing scheme?

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 ...
74 views

### 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$ ...
80 views

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

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$...
31 views

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

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 ...
626 views

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

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 ...
131 views

### 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, ...
86 views

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

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 ...
603 views

### More details about the Baillie–PSW test

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 ...
2k views

### 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 ...
577 views

### Efficiently computing the smallest integer with n divisors

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 ...
175 views

### Average runtime of naive primality test

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 true If $n$ is ...