Finding prime numbers with in a given number n.
I stumbled upon this question in Interviewstreet.com - looked very basic question, however I tried attempting it to check their editor. Later found that this was good question than I thought. The problem arises when N is = 1000000. We have to manage both memory and execution time.
-----------------------------------
For execution time to be optimized, used this algo for finding the prime numbers with in a given number. For memory modified it further to work in steps of 100000.
-------------------------------------
Write a function getNumberOfPrimes which takes in an integer N as its parameter,
to return the number of prime numbers that are less than N
Sample Testcases:
Input #00:
100
Output #00:
25
Input #01:
1000000
Output #01:
78498
----------------------------------------
Below is the solution. I have used php. I would add comments and optimize those loops further when I get some free time later.
-----------------------------------
No comment