Stack Overflow
Stack Overflow

Questions tagged [primes]

Primes or prime numbers are integers greater than 1 which are divisible only by themselves and 1, i.e.: 2, 3, 5, 7, 11, ... .

See Wikipedia on primes.

If your program for checking or computing prime numbers doesn't work, please check the following points before posting a question:

  • If it is too slow, try testing divisibility only up to and including the square root. If you want to compute all primes in a range better use the sieve of Eratosthenes, implemented properly it will be much faster.

  • If your algorithm says square numbers are prime you neglected the and including part above.

  • Check for overflow. n * n overflows a 32 bit signed integer for n > 46340. The sum of the first two million primes for Project Euler problem 10 will also overflow a 32 bit integer.

3346 questions
552
votes
13 answers

Why do we check up to the square root of a number to determine if the number is prime?

To test whether a number is prime or not, why do we have to test whether it is divisible only up to the square root of that number?
Pan
  • 6,455
  • 5
  • 27
  • 27
396
votes
40 answers

Fastest way to list all primes below N

This is the best algorithm I could come up. def get_primes(n): numbers = set(range(n, 1, -1)) primes = [] while numbers: p = numbers.pop() primes.append(p) numbers.difference_update(set(range(p*2, n+1, p))) …
jbochi
  • 28,816
  • 16
  • 73
  • 90
224
votes
20 answers

Which is the fastest algorithm to find prime numbers?

Which is the fastest algorithm to find out prime numbers using C++? I have used sieve's algorithm but I still want it to be faster!
kasperasky
  • 3,173
  • 5
  • 21
  • 16
210
votes
14 answers

Why are primes important in cryptography?

One thing that always strikes me as a non-cryptographer: Why is it so important to use prime numbers? What makes them so special in cryptography? Does anyone have a simple short explanation? (I am aware that there are many primers and that Applied…
Michael Stum
  • 177,530
  • 117
  • 400
  • 535
203
votes
9 answers

Why use a prime number in hashCode?

I was just wondering why is that primes are used in a class's hashCode() method? For example, when using Eclipse to generate my hashCode() method there is always the prime number 31 used: public int hashCode() { final int prime = 31; …
Ian Dallas
  • 12,451
  • 19
  • 58
  • 82
160
votes
30 answers

How to create the most compact mapping n → isprime(n) up to a limit N?

Naturally, for bool isprime(number) there would be a data structure I could query. I define the best algorithm, to be the algorithm that produces a data structure with lowest memory consumption for the range (1, N], where N is a constant. Just an…
Khaled Alshaya
  • 94,250
  • 39
  • 176
  • 234
137
votes
4 answers

How to determine if a number is a prime with regex?

I found the following code example for Java on RosettaCode: public static boolean prime(int n) { return !new String(new char[n]).matches(".?|(..+?)\\1+"); } I don't know Java in particular but understand all aspects of this snippet except for…
kitlite
  • 1,373
  • 2
  • 9
  • 4
101
votes
20 answers

Python Finding Prime Factors

Two part question: Trying to determine the largest prime factor of 600851475143, I found this program online that seems to work. The problem is, I'm having a hard time figuring out how it works exactly, though I understand the basics of what the…
francium
  • 2,384
  • 3
  • 20
  • 29
90
votes
25 answers

Most elegant way to generate prime numbers

What is the most elegant way to implement this function: ArrayList generatePrimes(int n) This function generates the first n primes (edit: where n>1), so generatePrimes(5) will return an ArrayList with {2, 3, 5, 7, 11}. (I'm doing this in C#, but…
David Johnstone
  • 24,300
  • 14
  • 68
  • 71
86
votes
1 answer

How does this regex find primes?

Possible Duplicate: How to determine if a number is a prime with regex? This page claims that this regular expression discovers non-prime numbers (and by counter-example: primes): /^1?$|^(11+?)\1+$/ How does this find primes?
Dinah
  • 52,922
  • 30
  • 133
  • 149
86
votes
6 answers

What is a possible use case of BigInteger's .isProbablePrime()?

The method BigInteger.isProbablePrime() is quite strange; from the documentation, this will tell whether a number is prime with a probability of 1 - 1 / 2^arg, where arg is the integer argument. It has been present in the JDK for quite a long time,…
fge
  • 119,121
  • 33
  • 254
  • 329
85
votes
24 answers

Sieve of Eratosthenes - Finding Primes Python

Just to clarify, this is not a homework problem :) I wanted to find primes for a math application I am building & came across Sieve of Eratosthenes approach. I have written an implementation of it in Python. But it's terribly slow. For say, if I…
Srikar Appalaraju
  • 71,928
  • 54
  • 216
  • 264
76
votes
12 answers

C - determine if a number is prime

I am trying to come up with a method that takes an integer and returns a boolean to say if the number is prime or not and I don't know much C; would anyone care to give me some pointers? Basically, I would do this in C# like this: static bool…
Jimmy
  • 9,686
  • 14
  • 59
  • 78
72
votes
9 answers

Given Prime Number N, Compute the Next Prime?

A coworker just told me that the C# Dictionary collection resizes by prime numbers for arcane reasons relating to hashing. And my immediate question was, "how does it know what the next prime is? do they story a giant table or compute on the fly?…
John Shedletsky
  • 7,110
  • 12
  • 38
  • 63
72
votes
12 answers

How to implement an efficient infinite generator of prime numbers in Python?

This is not a homework, I am just curious. INFINITE is the key word here. I wish to use it as for p in primes(). I believe that this is a built-in function in Haskell. So, the answer cannot be as naive as "Just do a Sieve". First of all, you do not…
Hamish Grubijan
  • 10,562
  • 23
  • 99
  • 147
1
2 3
…
99 100