Questions tagged [primes]
The primes tag has no usage guidance.
74
questions
0
votes
1answer
32 views
time complexity of Sieve of Eratosthenes
For https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithmic_complexity,
why time complexity = O(n*log(log n)) ?
1
vote
1answer
77 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)?...
0
votes
0answers
13 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
1answer
55 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...,\...
0
votes
1answer
30 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$ ...
2
votes
0answers
82 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 ...
2
votes
1answer
82 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 ...
2
votes
1answer
83 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?
<...
1
vote
2answers
135 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))$.
...
1
vote
1answer
37 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 ...
1
vote
3answers
68 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 ...
2
votes
2answers
98 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 ...
3
votes
1answer
634 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 ...
0
votes
2answers
90 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, ...
8
votes
3answers
2k 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?
3
votes
2answers
162 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
1answer
33 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 ...
1
vote
4answers
211 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 ...
2
votes
2answers
121 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
...
2
votes
2answers
203 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 ...
4
votes
1answer
155 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$ ...
2
votes
1answer
49 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 ...
1
vote
1answer
91 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 ...
1
vote
1answer
115 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 ...
1
vote
1answer
108 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 ...
1
vote
1answer
65 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$
...
2
votes
0answers
57 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$...
0
votes
0answers
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 ...
0
votes
0answers
500 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 ...
1
vote
2answers
116 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,
...
0
votes
1answer
75 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 ...
7
votes
3answers
440 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 ...
2
votes
3answers
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 ...
9
votes
2answers
339 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 ...
2
votes
1answer
155 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 ...
1
vote
1answer
111 views
Modifications to speed up the AKS primality proving
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 ...
5
votes
2answers
655 views
Express a number as a sum of consecutive primes (How many ways?)
I found this problem on codeforces in an ACM archive.
Given a number $n$, find the number possible of ways of expressing that number as a sum of consecutive primes. Example :
Given $n = 41$:
$41 = ...
0
votes
1answer
753 views
Is the given language decidable for turing machine?
I am going through undecidability of TM and found this question
$L=\left \{ \left \langle M \right \rangle |M\ is\ TM \ and \ number\ of\ strings\ in\ the\ language\ \ is\ prime\right \}$
I think it ...
-1
votes
3answers
543 views
Determine nth prime number in O(?)
If f(n) is the problem to determine the nth prime number, how fast can this be done, i.e.
What is the fastest known algorithm to find the nth prime number?
What are lower bounds for the time ...
1
vote
1answer
238 views
I have a problem understanding a solution for number theory problem from SPOJ [closed]
Problem statement can be found here or down below.
The solution which I'm trying to understand can be found here or down below.
Problem Statement.
Peter wants to generate some prime numbers for his ...
2
votes
0answers
51 views
Reference Request: Factorization of PseudoPrimes?
Is there any literature/survey/papers/books regarding the factorization of Strong PseudoPrimes (wrt. to a given base).
I am aware of the fact that weak Pseudo Primes can be factorized in Polynomial ...
1
vote
1answer
88 views
Is the prime factorization problem not an instance of the change making problem?
When using as the set of coins all logarithms of the prime numbers or numbers in general, and when using the logarithm of the number to be factored. The problem is just finding the logarithms that can ...
3
votes
3answers
2k views
Complexity of finding factors of a number
I have come up with two simple methods for finding all the factors of a number $n$. The first is trial division:
For every integer up to $\sqrt{n}$, try to divide by $d$, and if the remainder is $0$ ...
1
vote
1answer
711 views
How to compute Jacobi symbol efficiently?
How do I compute the Jacobi symbol $(N|A)$ efficiently?
In particular, for every odd $N, A$, define the Jacobi symbol $(A|N)$ as $\prod_i Q_{p_i}(A)$ where $p_1, \dots , p_k$ are all the (not ...
-1
votes
2answers
3k views
developing a Turing Machine that checks for powers of 2
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 ...
16
votes
2answers
1k views
Why is factoring large integers considered difficult?
I read somewhere that the most efficient algorithm found can compute the factors in $O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$ time, but the code I wrote is $O(n)$ or possibly $O(n \log n)$ ...
6
votes
1answer
803 views
What is the average-case complexity of trial division?
The trial division algorithm for checking if a number $N$ is prime works by trying to divide $N$ by all integers in the range 2, 3, ..., $\lfloor \sqrt{n} \rfloor$. If any of them cleanly divide $N$, ...
5
votes
2answers
3k views
What is the time complexity of checking if a number is prime?
Could some one please explain how to get the time complexity of checking if a number is prime? I'm really confused as to if it is $O(\sqrt{n})$ or $O(n^2)$.
I iterate from $i=2$ to $\sqrt{n}$ and ...
1
vote
1answer
760 views
Algorithm for generating coprime number sequences?
Does anyone know of an algorithm to generate a set of numbers of size $N$ which are all co-prime to eachother?
Ideally I'm looking for something that has random access abilities so i could ask for ...
3
votes
1answer
157 views
Worst-case prime sieve
The Sieve of Eratosthenes bothers me because you have to specify an upper bound before you begin the algorithm.
Is there a prime sieve that doesn't require this?
More Formally:
Is it possible to ...
