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, ... .
primes
3,361
questions
558
votes
13
answers
230k
views
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?
- 6,525
398
votes
41
answers
283k
views
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....
- 29.2k
227
votes
19
answers
397k
views
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!
- 3,201
211
votes
14
answers
204k
views
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 ...
- 179k
206
votes
9
answers
82k
views
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 ...
- 12.6k
161
votes
30
answers
286k
views
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 ...
- 95.5k
138
votes
4
answers
37k
views
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 ...
- 1,383
103
votes
21
answers
339k
views
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 ...
- 2,434
90
votes
25
answers
86k
views
Most elegant way to generate prime numbers [closed]
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 ...
- 24.4k
88
votes
26
answers
130k
views
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 ...
- 72.8k
87
votes
1
answer
29k
views
How does this regex find primes? [duplicate]
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+?)\...
- 53.4k
86
votes
6
answers
7k
views
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 ...
- 120k
76
votes
12
answers
207k
views
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 ...
- 9,766
72
votes
13
answers
34k
views
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 ...
- 10.6k
72
votes
9
answers
41k
views
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 ...
- 7,140
71
votes
6
answers
23k
views
What is a sensible prime for hashcode calculation?
Eclipse 3.5 has a very nice feature to generate Java hashCode() functions. It would generate for example (slightly shortened:)
class HashTest {
int i;
int j;
public int hashCode() ...
- 25.7k
70
votes
31
answers
308k
views
isPrime Function for Python Language
So I was able to solve this problem with a little bit of help from the internet and this is what I got:
def isPrime(n):
for i in range(2,int(n**0.5)+1):
if n%i==0:
return False
...
68
votes
32
answers
331k
views
Check if number is prime number
I would just like to ask if this is a correct way of checking if number is prime or not? because I read that 0 and 1 are NOT a prime number.
int num1;
Console.WriteLine("Accept number:");
num1 = ...
- 983
68
votes
5
answers
4k
views
Is a list (potentially) divisible by another?
Problem
Say you have two lists A = [a_1, a_2, ..., a_n] and B = [b_1, b_2, ..., b_n] of integers. We say A is potentially-divisible by B if there is a permutation of B that makes a_i divisible by b_i ...
- 1,202
67
votes
28
answers
232k
views
Simple prime number generator in Python
Could someone please tell me what I'm doing wrong with this code? It is just printing 'count' anyway. I just want a very simple prime generator (nothing fancy).
import math
def main():
count = ...
- 1,571
66
votes
0
answers
255k
views
Checking if a number is prime in Python [duplicate]
I have written the following code, which should check if the entered number is a prime number or not, but there is an issue I couldn't get through:
def main():
n = input("Please enter a ...
- 685
65
votes
31
answers
73k
views
Most efficient code for the first 10000 prime numbers?
I want to print the first 10000 prime numbers.
Can anyone give me the most efficient code for this?
Clarifications:
It does not matter if your code is inefficient for n >10000.
The size of the code ...
- 54.4k
63
votes
3
answers
40k
views
Reason for the number 5381 in the DJB hash function?
Can anyone tell me why the number 5381 is used in the DJB hash function?
The DJB hash function is defined as:
h 0 = 5381
h i = 33h i - 1 + s i
Here's a C implementation:
unsigned int DJBHash(char* ...
- 2,786
61
votes
41
answers
235k
views
How to find prime numbers between 0 - 100?
In Javascript how would i find prime numbers between 0 - 100? i have thought about it, and i am not sure how to find them. i thought about doing x % x but i found the obvious problem with that.
this ...
- 653
56
votes
9
answers
14k
views
Why is the size 127 (prime) better than 128 for a hash-table?
Supposing simple uniform hashing, that being, any given value is equally like to hash into any of the slots of the hash. Why is it better to use a table of size 127 and not 128? I really don't ...
- 4,926
54
votes
16
answers
84k
views
What would be the fastest method to test for primality in Java?
I am trying to find the fastest way to check whether a given number is prime or not (in Java). Below are several primality testing methods I came up with. Is there any better way than the second ...
- 10.2k
53
votes
2
answers
23k
views
How many prime numbers are there (available for RSA encryption)?
Am I mistaken in thinking that the security of RSA encryption, in general, is limited by the amount of known prime numbers?
To crack (or create) a private key, one has to combine the right pair of ...
- 1,047
49
votes
16
answers
18k
views
Fast Prime Number Generation in Clojure
I've been working on solving Project Euler problems in Clojure to get better, and I've already run into prime number generation a couple of times. My problem is that it is just taking way too long. I ...
- 14.5k
47
votes
12
answers
109k
views
Calculating and printing the nth prime number
I am trying to calculate prime numbers, which I've already done. But I want to calculate and print ONLY the nth prime number (User input), while calculating the rest (They won't be printed) only the ...
- 2,578
45
votes
13
answers
31k
views
nᵗʰ ugly number
Numbers whose only prime factors are 2, 3, or 5 are called ugly numbers.
Example:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
1 can be considered as 2^0.
I am working on finding nth ugly number. Note ...
- 1,313
44
votes
11
answers
19k
views
Speed up bitstring/bit operations in Python?
I wrote a prime number generator using Sieve of Eratosthenes and Python 3.1. The code runs correctly and gracefully at 0.32 seconds on ideone.com to generate prime numbers up to 1,000,000.
# from ...
- 17.4k
44
votes
8
answers
71k
views
Finding a prime number after a given number
How can I find the least prime number greater than a given number? For example, given 4, I need 5; given 7, I need 11.
I would like to know some ideas on best algorithms to do this. One method that ...
- 14.2k
42
votes
6
answers
34k
views
Segmented Sieve of Eratosthenes?
It's easy enough to make a simple sieve:
for (int i=2; i<=N; i++){
if (sieve[i]==0){
cout << i << " is prime" << endl;
for (int j = i; j<=N; j+=i){...
- 11.9k
40
votes
3
answers
23k
views
AKS Primes algorithm in Python
A few years ago, it was proven that PRIMES is in P. Are there any algorithms implementing their primality test in Python? I wanted to run some benchmarks with a naive generator and see for myself how ...
- 227k
39
votes
2
answers
2k
views
Recursive function causing a stack overflow
I am trying to write a simple sieve function to calculate prime numbers in clojure. I've seen this question about writing an efficient sieve function, but I am not to that point yet. Right now I am ...
- 60k
35
votes
36
answers
325k
views
Print series of prime numbers in python
I was having issues in printing a series of prime numbers from one to hundred. I can't figure our what's wrong with my code.
Here's what I wrote; it prints all the odd numbers instead of primes:
for ...
- 363
35
votes
2
answers
5k
views
Is Swift really slow at dealing with numbers?
As I was playing around with a swift tutorial, I started to write a custom isPrime method to check if a given Int is prime or not.
After writing it I realized it was working properly but found it a ...
- 9,873
34
votes
10
answers
39k
views
Fastest algorithm for primality test [closed]
I need to test primality on intervals between numbers which are really big (in the range of long long), so i need some fast algorithm for checking if a number is prime or not. Please suggest your ...
- 1,095
33
votes
28
answers
139k
views
Program to find prime numbers
I want to find the prime number between 0 and a long variable but I am not able to get any output.
The program is
using System;
using System.Collections.Generic;
using System.Linq;
using System....
- 3,415
33
votes
14
answers
274k
views
Prime number check acts strange [duplicate]
I have been trying to write a program that will take an imputed number, and check and see if it is a prime number. The code that I have made so far works perfectly if the number is in fact a prime ...
- 411
32
votes
1
answer
6k
views
Recursion with Func
Is it possible to do recursion with an Func delegate? I have the following, which doesn't compile because the name of the Func isn't in scope...
Func<long, long, List<long>, IEnumerable<...
- 10.1k
32
votes
1
answer
32k
views
What does "e is 65537 (0x10001)" mean?
I want to know what the output e is 65537 (0x10001) means. It happens during the RSA Key Generation using openssl genrsa. I know that the dots mean that the number has passed a probe division and the ...
- 1,183
29
votes
16
answers
17k
views
Is there a simple algorithm that can determine if X is prime?
I have been trying to work my way through Project Euler, and have noticed a handful of problems ask for you to determine a prime number as part of it.
I know I can just divide x by 2, 3, 4, 5, ..., ...
- 5,110
28
votes
10
answers
23k
views
Algorithm to find Lucky Numbers
I came across this question.A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between A and B are lucky? 1 <= A &...
- 507
28
votes
9
answers
21k
views
How to calculate the number of coprime subsets of the set {1,2,3,..,n}
I am solving this task (problem I). The statement is:
How many subsets of the set {1, 2, 3, ..., n} are coprime? A set of integers is called coprime if every two of its elements are coprime. Two ...
- 471
27
votes
3
answers
10k
views
Why setting HashTable's length to a Prime Number is a good practice?
I was going through Eric Lippert's latest Blog post for Guidelines and rules for GetHashCode when i hit this para:
We could be even more clever here; just as a List resizes itself when it gets full,...
- 18.3k
27
votes
5
answers
32k
views
Lazy List of Prime Numbers
How would one implement a list of prime numbers in Haskell so that they could be retrieved lazily?
I am new to Haskell, and would like to learn about practical uses of the lazy evaluation ...
- 16.5k
26
votes
15
answers
34k
views
How do I generate the first n prime numbers?
I am learning Ruby and doing some math stuff. One of the things I want to do is generate prime numbers.
I want to generate the first ten prime numbers and the first ten only. I have no problem ...
- 359
26
votes
11
answers
3k
views
How TDD works when there can be millions of test cases for a production functionality?
In TDD, you pick a test case and implement that test case then you write enough production code so that the test passes, refactor the codes and again you pick a new test case and the cycle continues.
...
- 26.7k
26
votes
1
answer
4k
views
Why do programming contests want answers modulo some large prime?
I have been testing the waters of competitive programming and I have already seen this statement mentioned a lot of times:
Print the result modulo 109 + 7
Now I can figure out that this is some ...
- 1,530