The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [primes]

The tag has no usage guidance.

75 questions
Filter by
Sorted by
Tagged with
65 views

...
118 views

Time complexity of Sieve of Eratosthenes [closed]

Wikipedia states that the Sieve of Eratosthenes runs in time $O(n\log\log n)$. Why is that so?
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)?...
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 ...
61 views

829 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 ...
577 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 ...
249 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 ...
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 ...
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 ...
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$ ...
752 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 ...
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 ...
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)$ ...
870 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$, ...
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 ...
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 ...