Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [primes]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
56
votes
4answers
45k 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 ...
23
votes
3answers
8k 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
6k 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
1k 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
200 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$ ...
10
votes
3answers
5k 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
377 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
471 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
883 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 ...
5
votes
2answers
686 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
156 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
87 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
3k 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
314 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
934 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
160 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
167 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
237 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
102 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
122 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
268 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
103 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
160 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
73 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
571 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
107 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
84 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
63 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
263 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
121 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
758 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
360 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
141 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
68 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
784 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
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)?...
1
vote
1answer
62 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
38 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
70 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
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 ...