Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [primes]

The tag has no usage guidance.

51
votes
4answers
41k views

Why is it best to use a prime number as a mod in a hashing function?

If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function $$ H = k \bmod \ 11$$ Now all the values will be placed ...
22
votes
3answers
7k views

When is the AKS primality test actually faster than other tests?

I am trying to get an idea of how the AKS primality test should be interpreted as I learn about it, e.g. a corollary for proving that PRIMES ⊆ P, or an actually practical algorithm for primality ...
21
votes
5answers
5k views

Data compression using prime numbers

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 ...
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)$ ...
13
votes
1answer
990 views

Is determining if there is a prime in an interval known to be in P or NP-complete?

I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval. However, does this mean that the ...
13
votes
3answers
197 views

Complexity-theoretic difficult of checking the value of $\pi(x)$?

The prime-counting function, demoted $\pi(x)$, is defined as the number of prime numbers less than or equal to $x$. We can define a decision problem from $\pi(x)$ as follows: Given two numbers $x$ ...
9
votes
3answers
4k views

Why Miller–Rabin instead of Fermat primality test?

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 ...
9
votes
2answers
326 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 ...
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?
7
votes
3answers
421 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 ...
6
votes
2answers
1k views

What is the name of this prime number algorithm?

Does the following recursive algorithm have a name? If so, what is it? ...
6
votes
1answer
746 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
2k 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 ...
5
votes
2answers
627 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 = ...
4
votes
3answers
5k views

What is the time complexity of generating n-th prime number?

Say I want to find the n-th prime. Is there an algorithm to directly calculate it or must I do with sieving? I know always calculate the next prime with a sieve principle, but what if I want the n-th ...
4
votes
1answer
154 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$ ...
4
votes
2answers
85 views

Assign unique integer keys to sets

I am given a list of $n>1$ arrays, where each array has fairly small number of elements (rarely above $5$). Also $n$ is quite small in practice (around $6$). My problem is that I would like to ...
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$ ...
3
votes
3answers
308 views

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

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 ...
3
votes
1answer
453 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 ...
3
votes
1answer
155 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 ...
3
votes
2answers
153 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 ...
2
votes
2answers
187 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 ...
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 ...
2
votes
2answers
90 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 ...
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
254 views

Finding coprimes closest to a certain target

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 ...
2
votes
1answer
69 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
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 ...
2
votes
1answer
153 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 ...
2
votes
1answer
70 views

Does there exist a problem that is hard to do in parallel? [closed]

I am looking for a workload which is hard to paralellise/distribute between multiple machines. For example, integer factorization does not go 10 times faster if you have 10 machines to split the ...
2
votes
1answer
564 views

Counting the number of N-dimensional coprime integer vectors

I am looking for an efficient way to count the number of coprime vectors in a finite and bounded set of integer vectors. The vectors in my set are $N$-dimensional integer vectors whose components are ...
2
votes
0answers
68 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

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? <...
2
votes
0answers
56 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$...
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
4answers
204 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 ...
1
vote
2answers
115 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, ...
1
vote
1answer
692 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
vote
1answer
350 views

Why don't people use Fermat's little theorem to check if number is prime?

There're a lot of examples of code for checking if a number is prime. Why don't people use Fermat's little theorem, i.e. this simple formula $\qquad a^{p-1} \equiv 1 \pmod p$, to check if a number ...
1
vote
2answers
132 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
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
56 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$ ...
1
vote
1answer
736 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 ...
1
vote
1answer
45 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...,\...
1
vote
1answer
32 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 ...
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
1answer
87 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
110 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 ...