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

13 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
  8. BestDewitt

    I have noticed you don’t monetize your website, don’t waste your traffic, you can earn extra cash every month because you’ve got hi quality content.
    If you want to know how to make extra $$$, search for: Ercannou’s essential adsense alternative

    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.

*