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

...
120 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

836 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 ...
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$ ...
578 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 ...
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 ...