Could someone please tell me what I&#39;m doing wrong with this code? It is just printing &#39;count&#39; anyway.  I just want a very simple prime generator (nothing fancy). 

    import math
    
    def main():
    	count = 3
    	one = 1
    	while one == 1:
    		for x in range(2, int(math.sqrt(count) + 1)):
    			if count % x == 0: 
    				continue
    			if count % x != 0:
    				print count
    				
    		count += 1

Simple prime number generator in Python

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 implementation(isPrime2)?

    public class Prime {
        public static boolean isPrime1(int n) {
            if (n &lt;= 1) {
                return false;
            }
            if (n == 2) {
                return true;
            }
            for (int i = 2; i &lt;= Math.sqrt(n) + 1; i++) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }
        public static boolean isPrime2(int n) {
            if (n &lt;= 1) {
                return false;
            }
            if (n == 2) {
                return true;
            }
            if (n % 2 == 0) {
                return false;
            }
            for (int i = 3; i &lt;= Math.sqrt(n) + 1; i = i + 2) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }
    }

    public class PrimeTest {
        public PrimeTest() {
        }
     
        @Test
        public void testIsPrime() throws IllegalArgumentException, IllegalAccessException, InvocationTargetException {
     
            Prime prime = new Prime();
            TreeMap&lt;Long, String&gt; methodMap = new TreeMap&lt;Long, String&gt;();
     
            for (Method method : Prime.class.getDeclaredMethods()) {
     
                long startTime = System.currentTimeMillis();
     
                int primeCount = 0;
                for (int i = 0; i &lt; 1000000; i++) {
                    if ((Boolean) method.invoke(prime, i)) {
                        primeCount++;
                    }
                }
     
                long endTime = System.currentTimeMillis();
     
                Assert.assertEquals(method.getName() + &quot; failed &quot;, 78498, primeCount);
                methodMap.put(endTime - startTime, method.getName());
            }
     
     
            for (Entry&lt;Long, String&gt; entry : methodMap.entrySet()) {
                System.out.println(entry.getValue() + &quot; &quot; + entry.getKey() + &quot; Milli seconds &quot;);
            }
        }
    }

What would be the fastest method to test for primality in Java?

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&#39;t understand what&#39;s the problem with the power of 2 numbers. Or how it actually makes any difference at all.

&gt; When  using  the  division  method, 
&gt; we  usually  avoid  certain  values 
&gt; of  m (table size). For example, m
&gt; should not be a power of 2, since if m
&gt; = 2^p  , then h(k) is just the p lowest-order bits of k.

Let&#39;s suppose the possible elements are only between 1 and 10000 and I picked the table size as 128. How can 127 be better?
So 128 is 2^6 (1000000) and 127 is 0111111. What difference does this make? All numbers (when hashed) are still going to be the p lowest-order bits of k for 127 too. Did I get something wrong?

I&#39;m looking for some examples as I really can&#39;t understand why is this bad. Thanks a lot in advance!

PS: I am aware of:
https://stackoverflow.com/questions/3980117/hash-table-why-size-should-be-prime

Why is the size 127 (prime) better than 128 for a hash-table?

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 prime numbers.

Is it impossible to publish a list of all the prime numbers in the range used by RSA? Or is that list sufficiently large to make this brute force attack unlikely? Wouldn&#39;t there be &quot;commonly used&quot; prime numbers?



How many prime numbers are there (available for RSA encryption)?

Which is the fastest algorithm to find out prime numbers using C++? I have used sieve&#39;s algorithm but I still want it to be faster!

Which is the fastest algorithm to find prime numbers?

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 Cryptography is the Bible, but as said: I am not looking to implement my own cryptographic algorithm, and the stuff that I found just made my brain explode - no ten pages of math formulas please).


Why are primes important in cryptography?

I was just wondering why is that primes are used in a class&#39;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;
         //...
    }

**References:**

Here is a good primer on Hashcode and article on how hashing works that I found (C# but the concepts are transferrable):
[Eric Lippert&#39;s Guidelines and rules for GetHashCode()][1]


  [1]: http://ericlippert.com/2011/02/28/guidelines-and-rules-for-gethashcode/

Why use a prime number in hashCode?

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 example of what I am looking for: I could represent every odd number with one bit e.g. for the given range of numbers (1, 10], starts at 3: `1110`  

The following dictionary can be squeezed more, right? I could eliminate multiples of five with some work, but numbers that end with 1, 3, 7 or 9 must be there in the array of bits. 

How do I solve the problem?


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

I found the following code example for Java on [RosettaCode][1]:

    public static boolean prime(int n) {
      return !new String(new char[n]).matches(&quot;.?|(..+?)\\1+&quot;);
    }


  [1]: http://rosettacode.org/wiki/Primality_by_trial_division#By_Regular_Expression


- I don&#39;t know Java in particular but understand all aspects of this snippet except for the regex itself
- I have basic to basic-advanced knowledge of Regex as you find it in the built-in PHP functions

How does `.?|(..+?)\\1+` match prime numbers?

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

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?

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

Two part question:

1) Trying to determine the largest prime factor of 600851475143, I found this program online that seems to work. The problem is, I&#39;m having a hard time figuring out how it works exactly, though I understand the basics of what the program is doing. Also, I&#39;d like if you could shed some light on any method you may know of finding prime factors, perhaps without testing every number, and how your method works.

Here&#39;s the code that I found online for prime factorization **[NOTE: This code is incorrect. See Stefan&#39;s answer below for better code.]**:

    n = 600851475143
    i = 2
    while i * i &lt; n:
         while n % i == 0:
             n = n / i
         i = i + 1

    print(n)

    #takes about ~0.01secs

2) Why is that code so much faster than this code, which is just to test the speed and has no real purpose other than that?

&lt;!-- to force the end of the list (item) in markdown --&gt;

    i = 1
    while i &lt; 100:
        i += 1
    #takes about ~3secs

Python Finding Prime Factors

What is the most elegant way to implement this function:

    ArrayList generatePrimes(int n)

This function generates the first `n` primes (edit: where `n&gt;1`), so `generatePrimes(5)` will return an `ArrayList` with `{2, 3, 5, 7, 11}`. (I&#39;m doing this in C#, but I&#39;m happy with a Java implementation - or any other similar language for that matter (so not Haskell)).

I do know how to write this function, but when I did it last night it didn&#39;t end up as nice as I was hoping. Here is what I came up with:

    ArrayList generatePrimes(int toGenerate)
    {
        ArrayList primes = new ArrayList();
        primes.Add(2);
        primes.Add(3);
        while (primes.Count &lt; toGenerate)
        {
            int nextPrime = (int)(primes[primes.Count - 1]) + 2;
            while (true)
            {
                bool isPrime = true;
                foreach (int n in primes)
                {
                    if (nextPrime % n == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    break;
                }
                else
                {
                    nextPrime += 2;
                }
            }
            primes.Add(nextPrime);
        }
        return primes;
    }

I&#39;m not too concerned about speed, although I don&#39;t want it to be obviously inefficient. I don&#39;t mind which method is used (naive or sieve or anything else), but I do want it to be fairly short and obvious how it works.

**Edit**: Thanks to all who have responded, although many didn&#39;t answer my actual question. To reiterate, I wanted a nice clean piece of code that generated a list of prime numbers. I already know how to do it a bunch of different ways, but I&#39;m prone to writing code that isn&#39;t as clear as it could be. In this thread a few good options have been proposed:

- A nicer version of what I originally had (Peter Smit, jmservera and Rekreativc)
- A very clean implementation of the sieve of Eratosthenes (starblue)
- Use Java&#39;s `BigInteger`s and `nextProbablePrime` for very simple code, although I can&#39;t imagine it being particularly efficient (dfa)
- Use LINQ to lazily generate the list of primes (Maghis)
- Put lots of primes in a text file and read them in when necessary (darin)

**Edit 2**: I&#39;ve [implemented in C#][1] a couple of the methods given here, and another method not mentioned here. They all find the first *n* primes effectively (and I have a [decent method][2] of finding the limit to provide to the sieves).


  [1]: https://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers/1072205#1072205
  [2]: https://stackoverflow.com/questions/1042717/is-there-a-way-to-find-the-approximate-value-of-the-nth-prime/1069023#1069023

Most elegant way to generate prime numbers

[The method `BigInteger.isProbablePrime()`][1] 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, so it means it must have uses. My limited knowledge in computer science and algorithms (and maths) tells me that it does not really make sense to know whether a number is &quot;probably&quot; a prime but not exactly a prime.

So, what is a possible scenario where one would want to use this method? Cryptography?


  [1]: http://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#isProbablePrime-int-

What is a possible use case of BigInteger&#39;s .isProbablePrime()?

Just to clarify, this is not a homework problem :)

I wanted to find primes for a math application I am building &amp; came across [**Sieve of Eratosthenes**][1] approach. 

I have written an implementation of it in Python. But it&#39;s terribly slow. For say, if I want to find all primes less than 2 million. It takes &gt; 20 mins. (I stopped it at this point). How can I speed this up?

    def primes_sieve(limit):
        limitn = limit+1
        primes = range(2, limitn)
    
        for i in primes:
            factors = range(i, limitn, i)
            for f in factors[1:]:
                if f in primes:
                    primes.remove(f)
        return primes
    
    print primes_sieve(2000)

**UPDATE:**
I ended up doing profiling on this code &amp; found that quite a lot of time was spent on removing an element from the list. Quite understandable considering it has to traverse the entire list (worst-case) to find the element &amp; then remove it and then readjust the list (maybe some copy goes on?). Anyway, I chucked out list for dictionary. My new implementation - 

    def primes_sieve1(limit):
        limitn = limit+1
        primes = dict()
        for i in range(2, limitn): primes[i] = True
    
        for i in primes:
            factors = range(i,limitn, i)
            for f in factors[1:]:
                primes[f] = False
        return [i for i in primes if primes[i]==True]

    print primes_sieve1(2000000)



  [1]: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes


Sieve of Eratosthenes - Finding Primes Python

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&#39;t know much C; would anyone care to give me some pointers?

Basically, I would do this in C# like this:
 
    static bool IsPrime(int number)
    {
        for (int i = 2; i &lt; number; i++)
        {
            if (number % i == 0 &amp;&amp; i != number)
                return false;
        }
        return true;
    }


C - determine if a number is prime

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)))
        return primes

    &gt;&gt;&gt; timeit.Timer(stmt=&#39;get_primes.get_primes(1000000)&#39;, setup=&#39;import   get_primes&#39;).timeit(1)
    1.1499958793645562

Can it be made even faster?

This code has a flaw: Since `numbers` is an unordered set, there is no guarantee that `numbers.pop()` will remove the lowest number from the set. Nevertheless, it works (at least for me) for some input numbers:

    &gt;&gt;&gt; sum(get_primes(2000000))
    142913828922L
    #That&#39;s the correct sum of all numbers below 2 million
    &gt;&gt;&gt; 529 in get_primes(1000)
    False
    &gt;&gt;&gt; 529 in get_primes(530)
    True

Fastest way to list all primes below N

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, &quot;how does it know what the next prime is? do they story a giant table or compute on the fly? that&#39;s a scary non-deterministic runtime on an insert causing a resize&quot;

So my question is, given N, which is a prime number, what is the most efficient way to compute the next prime number?

Given Prime Number N, Compute the Next Prime?

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() {
            final int prime = 31;
            int result = prime + i;
            result = prime * result + j;
            return result;
        }
    }

(If you have more attributes in the class, `result = prime * result + attribute.hashCode();` is repeated for each additional attribute. For ints .hashCode() can be omitted.)

This seems fine but for the choice 31 for the prime. It is probably taken from the [hashCode implementation of Java String][1], which was used for performance reasons that are long gone after the introduction of hardware multipliers. Here you have many hashcode collisions for small values of i and j: for example (0,0) and (-1,31) have the same value. I think that is a Bad Thing(TM), since small values occur often. For String.hashCode you&#39;ll also find many short strings with the same hashcode, for instance &quot;Ca&quot; and &quot;DB&quot;. If you take a large prime, this problem disappears if you choose the prime right.

So my question: what is a good prime to choose? What criteria do you apply to find it? 

This is meant as a general question - so I do not want to give a range for i and j. But I suppose in most applications relatively small values occur more often than large values. (If you have large values the choice of the prime is probably unimportant.) It might not make much of a difference, but a better choice is an easy and obvious way to improve this - so why not do it? Commons lang [HashCodeBuilder][2] also suggests curiously small values.

(**Clarification**: this is *not* a duplicate of [Why does Java&#39;s hashCode() in String use 31 as a multiplier?][1] since my question is not concerned with the history of the 31 in the JDK, but on what would be a better value in new code using the same basic template. None of the answers there try to answer that.)

  [1]: https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier
  [2]: http://commons.apache.org/proper/commons-lang/apidocs/org/apache/commons/lang3/builder/HashCodeBuilder.html

What is a sensible prime for hashcode calculation?

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 &quot;Just do a Sieve&quot;.

First of all, you do not know how many consecutive primes will be consumed. Well, suppose you could concoct 100 of them at a time. Would you use the same Sieve approach as well as the frequency of prime numbers formula?

I prefer non-concurrent approach.

Thank you for reading (and writing ;) )!


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

&gt; **Possible Duplicate:**  
&gt; [How to determine if a number is a prime with regex?](https://stackoverflow.com/questions/2795065/how-to-determine-if-a-number-is-a-prime-with-regex)  

&lt;!-- End of automatically inserted text --&gt;

&lt;a href=&quot;http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/&quot;&gt;This page&lt;/a&gt; claims that this regular expression discovers non-prime numbers (and by counter-example: primes):

    /^1?$|^(11+?)\1+$/

How does this find primes?

How does this regex find primes?

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` for all `i`. The problem is then: is it possible to reorder (i.e. permute) `B` so that `a_i` is divisible by `b_i` for all `i`?
For example, if you have

    A = [6, 12, 8]
    B = [3, 4, 6]

Then the answer would be `True`, as `B` can be reordered to be `B = [3, 6, 4]` and then we would have that `a_1 / b_1 = 2 `, `a_2 / b_2 = 2 `, and `a_3 / b_3 = 2 `, all of which are integers, so `A` is potentially-divisible by `B`.

As an example which should output `False`, we could have:

    A = [10, 12, 6, 5, 21, 25]
    B = [2, 7, 5, 3, 12, 3]

The reason this is `False` is that we can&#39;t reorder `B` as 25 and 5 are in `A`, but the only divisor in `B` would be 5, so one would be left out.

Approach
==============

Obviously the straightforward approach would be to get all the permutations of `B` and see if one would satisfy **potential-divisibility**, something along the lines of:

    import itertools
    def is_potentially_divisible(A, B):
      perms = itertools.permutations(B)
      divisible = lambda ls: all( x % y == 0 for x, y in zip(A, ls))
      return any(divisible(perm) for perm in perms)

Question
==============
What is the fastest way to know if a list is potentially-divisible by another list? Any thoughts? I was thinking if there&#39;s is a clever way to do this with **primes**, but I couldn&#39;t come up with a solution.

Much appreciated!


----------

*Edit*: It&#39;s probably irrelevant to most of you, but for the sake of completeness, I&#39;ll explain my motivation. In Group Theory there is a conjecture on finite simple groups on whether or not there is a bijection from irreducible characters and conjugacy classes of the group such that every character degree divides the corresponding class size. For example, for *U6(4)* [here are what `A` and `B` would look like.][1] Pretty big lists, mind you!


  [1]: https://gist.github.com/nachonavarro/cffc80ee2cf27cf6535d29b2dbfc9913

Is a list (potentially) divisible by another?

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&#39;t get through:

    def main():
        n = input(&quot;Please enter a number:&quot;)
        is_prime(n)

    def is_prime(a):
        x = True
        for i in (2, a):
                while x:
                   if a%i == 0:
                       x = False
                   else:
                       x = True


        if x:
            print(&quot;prime&quot;)
        else:
            print(&quot;not prime&quot;)

    main()

If the entered number is not a prime number, it displays &quot;not prime&quot;, as it is supposed to, but if the number is a prime number, it doesn&#39;t display anything. How can I fix this?





Checking if a number is prime in Python

I want to print the first 10000 prime numbers.
Can anyone give me the most efficient code for this?
Clarifications:

 1. It does not matter if your code is inefficient for n &gt;10000.
 2. The size of the code does not matter.
 3. You cannot just hard code the values in any manner.

Most efficient code for the first 10000 prime numbers?

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
            
        return True

But my question really is how to do it, but WHY. I understand that 1 is not considered a &quot;prime&quot; number even though it is, and I understand that if it divides by ANYTHING within the range it is automatically not a prime thus the return False statement. but my question is **what role does the squar-rooting the &quot;n&quot; play here**?

P.s. I am very inexperienced and have just been introduced to programming a month ago.

isPrime Function for Python Language

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 is what i have so far:
but unfortunately it is the worst code ever.

    var prime = function (){
	var num;
	for (num = 0; num &lt; 101; num++){
		if (num % 2 === 0){
			break;
		}
		else if (num % 3 === 0){
			break;
		}
		else if (num % 4=== 0){
			break;
		}
		else if (num % 5 === 0){
			break;
		}
		else if (num % 6 === 0){
			break;
		}
		else if (num % 7 === 0){
			break;
		}
		else if (num % 8 === 0){
			break;
		}
		else if (num % 9 === 0){
			break;
		}
		else if (num % 10 === 0){
			break;
		}
		else if (num % 11 === 0){
			break;
		}
		else if (num % 12 === 0){
			break;
		}
		else {
			return num;
		}
	}
    };
    console.log(prime());

How to find prime numbers between 0 - 100?

Can anyone tell me why the number 5381 is used in the DJB hash function?

The DJB hash function is defined as:

- h&lt;sub&gt; 0&lt;/sub&gt; = 5381

- h&lt;sub&gt; i&lt;/sub&gt; = 33h&lt;sub&gt; i - 1&lt;/sub&gt; + s&lt;sub&gt; i&lt;/sub&gt;

Here&#39;s a C implementation:

```c
unsigned int DJBHash(char* str, unsigned int len)
{
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for(i = 0; i &lt; len; str++, i++)
   {   
      hash = ((hash &lt;&lt; 5) + hash) + (*str);
   }   

   return hash;
}
```

Reason for the number 5381 in the DJB hash function?

 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(&quot;Accept number:&quot;);
    num1 = Convert.ToInt32(Console.ReadLine());
    if (num1 == 0 || num1 == 1)
    {
        Console.WriteLine(num1 + &quot; is not prime number&quot;);
        Console.ReadLine();
    }
    else
    {
        for (int a = 2; a &lt;= num1 / 2; a++)
        {
            if (num1 % a == 0)
            {
                Console.WriteLine(num1 + &quot; is not prime number&quot;);
                return;
            }

        }
        Console.WriteLine(num1 + &quot; is a prime number&quot;);
        Console.ReadLine();
    }

All Primes Solutions on Gang of Coders

Total of 27 Primes Solutions