CareerCup

Using Sieve of Eratosthenes algorithm:

1. Create an array container to hold all of the prime numbers you have found.
2. As you start your loop eliminate, 1, 2, 3, and any number divisible by them. When you get to another prime number, like 5, add it to your array of prime numbers.
3. For every number you encounter, if it cannot be divided by any number in your array of primes, it is prime. Add it to your array.

Worst-case running time, I believe is O(n^2).

In python:

def FindPrime(n):
      ''' n is the maximum number that you want check up to, otherwise this become an infinitely looping algorithm'''
      
      primes = [2, 3]
      
      for num in range(4, n):
        notprime = False
      	for p in primes:
      		if num % p == 0:
      			notprime = True
      	if notprime == False:
      		primes.append(num)
      
      print primes
        
print FindPrime(100)

The fastest algorithm for finding prime numbers is the Sieve of Atkin (explained in wikipedia).

I checked around online and the first answer I gave is actually finding prime numbers using trial division. Here is a verified sieve of eratosthnese algorithm in python:

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in xrange(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

Void CountPrimeNumber(int n)
{
int count = 2;
for (int i = 3; i<=n; i++)
{
for(int j = 2; j<=sqrt(i); j++)
{
if ((i%j) == 0)
break;
else
count++;
}
}
}

void findPrime(unsigned long n, vector<long>& result)
{
	if (n <= 3) {
		result.push_back(2);
		result.push_back(3);
	} else {
		long double j;
		result.push_back(2);
		result.push_back(3);
		for (long i = 4; i <= n; i++) {
			long double sqrtI = sqrt(i);
			for (j = 2; j <= sqrtI && (i % (long)j); j++);
			if (j >= sqrtI && (i % (long)j))
				result.push_back(i);
		}
	}
}