Most elegant way to generate prime numbers [closed]

by

Use the estimate

pi(n) = n / log(n)

for the number of primes up to n to find a limit, and then use a sieve. The estimate underestimates the number of primes up to n somewhat, so the sieve will be slightly larger than necessary, which is ok.

This is my standard Java sieve, computes the first million primes in about a second on a normal laptop:

public static BitSet computePrimes(int limit)
{
    final BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++)
    {
        if (primes.get(i))
        {
            for (int j = i * i; j < limit; j += i)
            {
                primes.clear(j);
            }
        }
    }
    return primes;
}

More Related Contents:

  1. C#: How to make Sieve of Atkin incremental
  2. Different combinations of an array (C#)
  3. Algorithm to detect overlapping periods [duplicate]
  4. Which is the fastest algorithm to find prime numbers?
  5. Why is Multiple Inheritance not allowed in Java or C#?
  6. Select N random elements from a List in C#
  7. How to find all partitions of a set
  8. How would you code an efficient Circular Buffer in Java or C#?
  9. Quick and Simple Hash Code Combinations
  10. Check if number is prime number
  11. Where can I find a Java to C# converter? [closed]
  12. C# hashcode for array of ints
  13. What are major differences between C# and Java?
  14. What are checked exceptions in Java/C#?
  15. Efficient Cartesian Product algorithm
  16. Difference between namespace in C# and package in Java
  17. Best hashing algorithm in terms of hash collisions and performance for strings
  18. Printing prime numbers from 1 through 100
  19. LINQ to find series of consecutive numbers
  20. How to read a .NET Guid into a Java UUID
  21. How does creating a instance of class inside of the class itself works?
  22. DirectoryInfo.EnumerateFiles(…) causes UnauthorizedAccessException (and other exceptions)
  23. Why should casting be avoided? [closed]
  24. C#: Seeking PNG Compression algorithm/library [closed]
  25. Memory-constrained external sorting of strings, with duplicates combined&counted, on a critical server (billions of filenames)
  26. Find if point lies on line segment
  27. What’s the quickest way to compute log2 of an integer in C#?
  28. Sorting a linked list
  29. Creating your own Tinyurl style uid
  30. RSA read PublicKey

Leave a Comment