# 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
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
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
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...)
0
Author 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
Commented:

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

thanks, mark
0
Commented:
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
Commented:
How did you implement the algorithm, and what non-primes are you getting in the list?
0
Author 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.

mark
0
Commented:
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
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...)

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

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Author Commented:

mark
0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.