Questions tagged [primes]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
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 ...
13
votes
3answers
198 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$ ...
-1
votes
1answer
31 views

How n (1+b) is not prime? [closed]

Here is the complete proof taken from this link How do I convince myself that n(1+b) is not prime when b>=1? Here is what I did: if n is 3 and b is 3. Then ...
2
votes
1answer
72 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
2answers
264 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 ...
0
votes
1answer
372 views

conversion to base-R numbers

I am reading Algorithms 4th edition by Robert Sedgewick and am stumped at a particular problem. On page 460 of the book the author is describing a technique to hash strings and use prime numbers for ...
1
vote
0answers
325 views

Can the Sieve of Eratosthenes be adapted to find twin primes

The Sieve of Eratosthenes is an algorithm generate the prime numbers, $2,3,5,7,11,13,...$ by drawing a list of numbers crossing out multiples of the smallest number in the list. Is there anyway to ...
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? ...
0
votes
1answer
148 views

Python Prime Numbers Code Problem [closed]

I was trying to write my own code for primes in Python. I know that code already exists, but I am doing this to challenge my knowledge and make my own solution. I was wondering if any of you guys ...
0
votes
1answer
322 views

Algorithm to find and add prime numbers

How would one write code to find and add the prime numbers between 4 and 5 million? I need a code that can find all such numbers, and then add them together. I'm not too keen on computer science, so I ...
22
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 ...
0
votes
1answer
142 views

Finding prime factors of non-random key generator

I have been working on a challenge i found on the internet. It is as follows: You've stumbled onto a significant vulnerability in a commonly used cryptographic library. It turns out that the random ...
1
vote
1answer
137 views

Proving that collision is less likely if the table size is prime in case modulo arithmetic is used

If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets, ...
10
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 ...
1
vote
1answer
138 views

Fast ways to compute the smallest prime with a given substring?

So, I've got this problem: Given a string $\omega\in\{0,\ldots,9\}^*$, find the smallest prime number (in base 10) that contains that string, or otherwise returns 0. What I'm asking is a fast ...
1
vote
1answer
354 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 ...
0
votes
1answer
2k views

Sieve of Eratosthenes vs. Sieve of Sundaram

Relevant Information: Sieve of Eratosthenes Sieve of Sundaram Suppose I want to generate all primes in [2,n], and I have both of these algorithms at my disposal to ...
2
votes
1answer
569 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 ...
0
votes
1answer
82 views

Finding largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$

I need to find largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$ where $N$ can be as large as $10^{18}$. I tried this approach , but is too slow. Finding the just smallest prime number to $N$, ...
3
votes
3answers
312 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 ...
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 ...
54
votes
4answers
43k 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 ...
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 ...