Trouble w/ prime number algorithm

i'm not looking for someone to explicitly answer this but a few hints would be great.  i'm trying to write a couple of functions for determining prime numbers.  the first asks for the user to enter an integer which is passed to a function with a return value indicating whether the integer is a prime or not.  before i pass the integer i determine if it's even using i%2 approach.  if it is even (except 2) i don't send it, i just cout that it's not a prime.
once the int is passed to the function it's assumed to be odd and cannot be divided by an even number so i set up a for loop to modulus by only odd numbers 3,5,7 and 9 with 0 remainder returning to the calling function that the number is not prime.
second is an algorithm to calculate all primes between 2 and 10000.
my problem is that i get on occasion in the list of primes a few that are not primes.
can someone set me off in the right direction?  thanks, mark
markxAsked:
Who is Participating?
 
joshaubryConnect With a Mentor Commented:
think of it this way, every number that is not prime is divisible by a prime so, use a queue or stack or something, initialize with the first few primes (like up to 11) and go through the odd numbers to 10000, testing by dividing by all the numbers in the queue, adding the number to the queue if it is prime and rejecting it if it is not...

                        (i hope i didnt say too much...)

ok... well, think about this, you weeded out all the even numbers,
so for any particular odd number, it will be divisible by only odd numbers
but you can narrow it down more than that... the numbers that divide it have to be less than its square root

i.e. say if you were checking if 5249 is a prime...  take its square root (which is 72.45) and divide it by every odd number between 3 and the square root....so start at 3 and go to 71, if none of those divide it then it is prime...

to gothick... thats what i was going to teach him before i found out he hadnt go to any container classes yet... (i had just forgotten the name of it, but the algorithm is in my STL book if anyone wants it)
0
 
PIGCommented:
You have a problem with Your algorithm. Prime is that number that can not devide with not a one of prime that is smalles him. Try this. I think that work.
0
 
joshaubryCommented:
think of it this way, every number that is not prime is divisible by a prime

so, use a queue or stack or something, initialize with the first few primes (like up to 11) and go through the odd numbers to 10000, testing by dividing by all the numbers in the queue, adding the number to the queue if it is prime and rejecting it if it is not...

(i hope i didnt say too much...)
0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
markxAuthor Commented:
i'm way more basic than queues and stacks at this point.  i'm very new at programming in c++ (or any language for that matter).

mark
0
 
joshaubryCommented:
how about using an array

if u want details, just ask...
0
 
markxAuthor Commented:
can't use arrays yet.  next chapter.

thanks, mark
0
 
joshaubryCommented:
ok... well, think about this, you weeded out all the even numbers, so for any particular odd number, it will be divisible by only odd numbers

but you can narrow it down more than that... the numbers that divide it have to be less than its square root

i.e. say if you were checking if 5249 is a prime...  take its square root (which is 72.45) and divide it by every odd number between 3 and the square root....so start at 3 and go to 71, if none of those divide it then it is prime
0
 
ozoCommented:
How did you implement the algorithm, and what non-primes are you getting in the list?
0
 
markxAuthor Commented:
to joshaubry - please repost your answer so i can close it to you.  actually helped a lot and the resulting code is even fairly tight.

thanks for your input.

mark
0
 
gothickCommented:
MarkX: Probably teaching you to suck eggs, here, but when you get to arrays, try doing a web search for Eratosthenes' Sieve -- a very smart way of finding primes.
0
 
markxAuthor Commented:
arrays, classes, overloading...can't wait.  thanks!

mark
0
All Courses

From novice to tech pro — start learning today.