Questions tagged [primes]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
9
votes
2answers
566 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
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 ...
1
vote
1answer
130 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 ...
2
votes
1answer
174 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 ...
3
votes
3answers
344 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 ...
2
votes
2answers
317 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 ...
5
votes
2answers
788 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
1k 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 ...
13
votes
3answers
220 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
3answers
684 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
322 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
53 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 ...
5
votes
2answers
4k 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
108 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
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$ ...
1
vote
1answer
1k 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 ...
17
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)$ ...
7
votes
1answer
1k 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$, ...
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 ...
1
vote
1answer
851 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
175 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 ...
-1
votes
1answer
33 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
76 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 ...
0
votes
1answer
378 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
345 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
170 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 ...
1
vote
1answer
330 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 ...
1
vote
1answer
143 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, ...
0
votes
1answer
149 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
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
394 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 ...
2
votes
1answer
594 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
84 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$, ...
4
votes
2answers
102 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 ...

1
2