There are many ways to create a prime numbers. However, the time constraints will reflect your skill to create an algorithm. Whereas I am a student of computer science, the algorithm should meet time efficiency. I am sure that all of you already had project about prime numbers. In the following examples, I will be using the Python2.5 programming language to demonstrate such algorithms and compare their efficiencies. Later I will also update it into C/C++ and Java languages.

The first algorithm we shall consider will begin with the integer 2 and proceed to select each successive integer as a potential prime, (pp), checking for primacy by testing to see if it can be factored by any previously identified primes, then storing each newly verified prime in a prime set (ps) array.

pp=2
ps=[pp]
lim=raw_input(“\nGenerate prime numbers up to what number? : “)
while pp<int(lim):
pp+=1
test=True
for a in ps:
if pp%a==0: test=False
if test: ps.append(pp)
return ps
Note: The code given above does not constitute a complete program. See Appendix A for a complete program including a user interface.
Such a rudimentary algorithm takes a strictly brute force approach to effectively achieve the goal of identifying each prime number and storing it in an array. I am sure you would agree that this is also about the least efficient means of generating prime numbers.
Advertisement