Finding prime numbers

Output all prime numbers up to a specified integer n.

This is a phone screen question from one of my interviews. An efficient way to generate prime numbers is using Sieve of Eratosthenes. We store the primes in a table of true false values, so we are able to determine if a number is a prime number efficiently using this table.

Below is one possible implementation, you can read more in-depth analysis about generating prime numbers in Programming Pearls.

VN:F [1.9.22_1171]
Rating: 4.5/5 (21 votes cast)
Finding prime numbers, 4.5 out of 5 based on 21 ratings

11 thoughts on “Finding prime numbers

  1. learner

    Hi ,
    The above solution works well when we n not large like millions .
    For large number what could be the approach to solve this problem ?

    VA:F [1.9.22_1171]
    0
    1. Liang

      I’ve afraid there’s no known algorithm that can be used to efficiently determine if a large integer is prime or not.

      VA:F [1.9.22_1171]
      0
  2. homeloveyou501

    VN:F [1.9.22_1171]
    0
  3. Mingliang LIU

    VN:F [1.9.22_1171]
    0
  4. beenu maharjan

    public List FindPrimeNumbers(int n) {
    List primelist = new ArrayList();

    if (n <= 1) {
    return primelist;
    }
    if (n <= 3) {
    primelist.add(2);
    if (n == 3) {
    primelist.add(3);
    }

    return primelist;
    }

    // For n greater than 3
    primelist.add(2);
    primelist.add(3);

    int m = 5;
    while (m <= n) {
    if (IsPrime(m, primelist)) {
    primelist.add(m);
    System.out.print(m);

    }
    m = m + 2;

    }

    return primelist;
    }

    public boolean IsPrime(int n, List plist) {
    int temp = n / 3;
    for (int i = 1; i temp) {
    return true;
    }
    }
    return true;

    }

    VA:F [1.9.22_1171]
    +2
  5. l@zy5w@pp3r

    @ Mingliang LIU
    Your code is totally optimized except one place
    for (int j = i * i; j <= n; j += i)
    since j += i will be even so we can ignore it and advance the counter by 2i instead of i

    void prime_sieve2(int n, bool prime[]) {
    prime[0] = prime[1] = false;
    prime[2] = true;
    for (int i = 3; i <= n; i++)
    prime[i] = (i % 2);

    int limit = sqrt(n);
    for (int i = 3; i <= limit; i += 2)
    if (prime[i])
    for (int j = i * i; j <= n; j += 2i) // since j += i will be even so we can ignore it
    prime[j] = false;
    }

    VA:F [1.9.22_1171]
    +1
  6. Pingback: Algorithms » Tech Blog

  7. Noob

    My code gives Time Limit Exceeded error, can anyone help me what’s the problem?

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*