Prime Number, what's wrong with these code?

[baltimoredude1]

Hi

I was writing a simple code to generate the first 100 prime numbers.
Everything looks fine to me except the output of the program. What's
wrong with it? I am attaching the program as well as the output. Would
appreciate if someone could mail me at baltimo...@gmail.com

Thanks
A M Rahman

//------------------------------------------------------------------------------------------------------------------------------------------

#include<iostream.h>
#include<process.h>

int prime(int number);

int main(void)
{

int counter = 0;

for (int n = 2; n < 1000; n++)
{
if ( prime(n) == 1 )
{
cout << n << " ";
counter ++;
if (counter > 99)
{
exit(0);
}

} // close if
} // close for

return 0;
} // close main

int prime(int number)
{

for (int i = 2; i <= number -1 ; i++)
{
if (number % i != 0)
{
return 1;
}

else
{
return 0;
}
} // close for
}

-----------------------------------------------------------------------------------------------------------------------------------//

output

2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49
51 53 55
57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101
103 105
107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141
143 145
147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177 179 181
183 185
187 189 191 193 195 197 199

[Jerry Coffin]

In article <1154123004.5...@m79g2000cwm.googlegroups.com>,
baltimo...@gmail.com says...

[ ... ]

> int prime(int number)
> {
>
> for (int i = 2; i <= number -1 ; i++)
> {
> if (number % i != 0)
> {
> return 1;
> }
>
> else
> {
> return 0;
> }

Your logic here is wrong -- you should only return 1 after you've
determined that the number doesn't evenly divide _any_ of the numbers
you try it against. Right now, you've written the code so it always
returns after only one iteration.

There are a number of other things you can do to make this faster as
well -- one is to observe that if a number has any divisors, at least
one of them must be less than or equal to the square root of the
number. Another is to note that a number that isn't divisible by 2
won't be divisible by any other even number either.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[rossum]

On 28 Jul 2006 14:43:24 -0700, "baltimoredude1"
<baltimo...@gmail.com> wrote:

>Hi
>
>I was writing a simple code to generate the first 100 prime numbers.
>Everything looks fine to me except the output of the program. What's
>wrong with it? I am attaching the program as well as the output. Would
>appreciate if someone could mail me at baltimo...@gmail.com

This is usenet, replies are usually to the group rather than by
e-mail.

>
>Thanks
>A M Rahman
>
>//---------------------------------------------------------------
>
[snip]

>int prime(int number)
>{
>
> for (int i = 2; i <= number -1 ; i++)
> {
> if (number % i != 0)
> {
> return 1;
> }
>
> else
> {
> return 0;
> }
> } // close for
>}

1 Your program flags 9 as prime, which is wrong. Step through this
function yourself on paper with number = 9. How many times is the
for-loop executed? Do a bit more research:- What happens if number
is even? What happens if number is odd?

2 Explain why 2 is the only even number output by your program.

3 What happens if number is 1, 0, negative?

rossum

[Richard Heathfield]

rossum said:

<snip>

>
> 1 Your program flags 9 as prime, which is wrong.

9 /is/ prime. Ask any engineer! :-)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[J_Smith]

Jerry Coffin wrote:
> In article <1154123004.5...@m79g2000cwm.googlegroups.com>,
> baltimo...@gmail.com says...
>
> [ ... ]
>
>
>>int prime(int number)
>>{
>>
>> for (int i = 2; i <= number -1 ; i++)
>> {
>> if (number % i != 0)
>> {
>> return 1;
>> }
>>
>> else
>> {
>> return 0;
>> }
>
>
> Your logic here is wrong -- you should only return 1 after you've
> determined that the number doesn't evenly divide _any_ of the numbers
> you try it against. Right now, you've written the code so it always
> returns after only one iteration.

Listen to this man for he is wise. I won't give you the answer since
this smells like homework but the fix is very simple. Unfortunatly it's
the simple problems that seem to be that hardest to fix! Without giving
too much away you've basically written a complex function that tells you
if a number is odd. Oddest thing is that when i run your code thru
Dev-C++ it goes from 3 - 201 instead of 2 - 199.

[Stuart Golodetz]

"J_Smith" <u...@sorry.no> wrote in message
news:TtSyg.486$48....@bignews7.bellsouth.net...

That's because the prime(2) call invokes undefined behaviour (6.6.3).
Specifically, the for loop is never entered (because 2 > number-1 = 2-1 = 1)
and control flows off the end of the function.

[Somewhat OT, but possibly marginally relevant]

After doing some experimenting: In VC++ 2005, the last value stored in the
EAX register (and thus the value returned) is 1 (apparently the "number-1"
in the loop condition), thus the call prime(2) returns 1 and 2 gets counted
as a prime. Changing the condition to i<number, which would seem to be
equivalent, changes the behaviour of the program...now the function returns
2 instead (ouch). Of course, exactly how values get returned from functions
depends on your platform, I'm just illustrating the point with the compiler
I had to hand.

Regardless of how values are returned, when the function returns anything
other than 1 (e.g. in Dev-C++), which it's perfectly entitled to, since it's
undefined what should happen, 3-201 will be printed instead of 2-199,
because 100 numbers are printed, so 2 gets ignored and an extra number gets
added on the end.

[/Somewhat OT]

Hope this helps,
Stu

[apollo]

I think there is something wrong with the function prime,it return too
many values and may not be the one you want to get or return.I write
the following code:
int prime(int number)
{
int flags = 1;

for (int i = 2; i <= number -1 ; i++)
{

if (number % i == 0)
{
flags = 0;
}

} // close for
return flags;
}
I don't know this is wheather you want to get.

[James Dennett]

apollo wrote:

[snip]

> I think there is something wrong with the function prime,it return too
> many values and may not be the one you want to get or return.I write
> the following code:
> int prime(int number)
> {
> int flags = 1;
> for (int i = 2; i <= number -1 ; i++)
> {
> if (number % i == 0)
> {
> flags = 0;
> }
>
> } // close for
> return flags;
> }
> I don't know this is wheather you want to get.

One small note: this isn't terrible, assuming we ignore the
indentation problems that are probably a side-effect of the
newsgroup format and newsreader problems, but "flags" is one
example of a variable name that can almost always be improved;
in this case, calling it "is_prime" or "no_factors_found"
would be clearer. (It might be even clearer to call it
"factors_found" and set it to zero initially; code can
often be clarified by changing a negative to a positive.)

-- James

[Francis Glassborow]

In article <1154316757.5...@h48g2000cwc.googlegroups.com>,
apollo <cxy...@tom.com> writes

>I think there is something wrong with the function prime,it return too
>many values and may not be the one you want to get or return.I write
>the following code:
> int prime(int number)
> {
> int flags = 1;
> for (int i = 2; i <= number -1 ; i++)
> {
> if (number % i == 0)
> {
> flags = 0;
> }
>
> } // close for
> return flags;
>}
>I don't know this is wheather you want to get.

There are many things that can be done to improve the efficiency of a
prime number generator. However here is a simple isprime function that
can be used for starters.

bool isprime(int number){
if(number < 2) return false; // deals with 1, 0 and negative values
if(number == 2) return true; // deals with 2 as a special case
int limit == sqrt(number) + 1;
for (int i = 0; i < limit; i += 2){
if(number % i) == 0) return false;
}
return true;
}

Yes those advocating single entry single exit style programming will not
like this because the function contains 4 return statements :-) However
using auxiliary variables is about as bad, IMHO.

If I were writing in C++, I would probably use a vector to store primes
as they were computed and use that as a source of test divisors.

--
Francis Glassborow ACCU
Author of 'You Can Do It!' and "You Can Program in C++"
see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects

[Richard Heathfield]

Francis Glassborow said:

<snip>

>
> There are many things that can be done to improve the efficiency of a
> prime number generator. However here is a simple isprime function that
> can be used for starters.
>
> bool isprime(int number){
> if(number < 2) return false; // deals with 1, 0 and negative values
> if(number == 2) return true; // deals with 2 as a special case
> int limit == sqrt(number) + 1;
> for (int i = 0; i < limit; i += 2){
> if(number % i) == 0) return false;
> }
> return true;
> }
>
> Yes those advocating single entry single exit style programming will not
> like this

Correct. I am one such.

> because the function contains 4 return statements :-)

I think there are more important reasons not to like it, such as the
incorrect use of ==, the mismatched parentheses, and (after those are
corrected) the division by 0 which dumps core all over my shell.

[Stuart Golodetz]

"Francis Glassborow" <fra...@robinton.demon.co.uk> wrote in message
news:7bVhIiP0...@robinton.demon.co.uk...

> In article <1154316757.5...@h48g2000cwc.googlegroups.com>,
> apollo <cxy...@tom.com> writes
>>I think there is something wrong with the function prime,it return too
>>many values and may not be the one you want to get or return.I write
>>the following code:
>> int prime(int number)
>> {
>> int flags = 1;
>> for (int i = 2; i <= number -1 ; i++)
>> {
>> if (number % i == 0)
>> {
>> flags = 0;
>> }
>>
>> } // close for
>> return flags;
>>}
>>I don't know this is wheather you want to get.
>
>
> There are many things that can be done to improve the efficiency of a
> prime number generator. However here is a simple isprime function that
> can be used for starters.
>
> bool isprime(int number){
> if(number < 2) return false; // deals with 1, 0 and negative values
> if(number == 2) return true; // deals with 2 as a special case
> int limit == sqrt(number) + 1;
> for (int i = 0; i < limit; i += 2){
> if(number % i) == 0) return false;
> }
> return true;
> }

Did you mean something a bit more like

bool is_prime(int n)
{
if(n == 2) return true;
if((n < 2) || (n % 2 == 0)) return false;

int limit = (int)floor(sqrt((double)n));

for(int i=3; i<=limit; i+=2)
{
if(n % i == 0) return false;
}

return true;
}

?

> Yes those advocating single entry single exit style programming will not
> like this because the function contains 4 return statements :-) However
> using auxiliary variables is about as bad, IMHO.

I've never really seen what the big deal is as far as the whole single exit
thing is concerned. (I'd be more than happy to hear some sort of
justification from someone if they're that way inclined.) I've always been
inclined to use whatever's clearest in a given context. Then again, I've
been inclined to commit many programming mistakes in the past until someone
pointed out what I was doing wrong. Am I missing something in this instance?

> If I were writing in C++, I would probably use a vector to store primes
> as they were computed and use that as a source of test divisors.

Why a vector rather than a list? Appending to a list would be faster surely?

void find_primes(std::list<int>& primes, unsigned int primesToFind)
{
primes.clear();
primes.push_back(2);

for(int n=3; primes.size() < primesToFind; n+=2)
{
int limit = (int)floor(sqrt((double)n));

bool isPrime = true;
for(std::list<int>::const_iterator it=primes.begin(),
iend=primes.end(); it!=iend && *it <= limit; ++it)
{
if(n % *it == 0) isPrime = false;
}

if(isPrime) primes.push_back(n);
}
}

Cheers,
Stu

[rossum]

Me too! Me too!

// Test for prime
bool isPrime(int num) {
// Negatives, zero, unity, evens and multiples of three
if (num < 2) { return false; }
switch (num % 6) {
case 0: return false;
case 1: break;
case 2: return 2 == num;
case 3: return 3 == num;
case 4: return false;
case 5: break;
} // end switch

// Look for factors of 5, 7 etc.
long trialFac = 5; // Current trial factor
long increment = 2; // Increment for trial factor
long sqrtNum = mjr::isqrt(num); // Integer square root of num
while (trialFac <= sqrtNum) {
// Check num against current trial factor
if (0 == (num % trialFac)) { return false; }

// Go to next trial factor
trialFac += increment; // Next trial factor
increment = 6 - increment; // Add 2, 4 alternating
} // end while

return true; // num is prime if we reach here
} // end isPrime()

rossum

[James Dennett]

Stuart Golodetz wrote:
>
> Why a vector rather than a list? Appending to a list would be faster surely?

Did you try timing that? It would be an interesting exercise.
std::list has to perform a dynamic allocation for each item
added, and a std::list<int> has considerable size overhead and
is much less cache-friend that the contiguous storage in a
std::vector<int>.

If you're worried about the cost of a vector copying elements,
don't be (at least, not without profiling). On average each
item is copied once (or less), and copying an int is very
cheap indeed compared to dynamic memory allocation.

I've not measured either, but I do suspect that pushing back
a large number of items to a vector will be much faster than
for a list.

-- James

[Francis Glassborow]

In article <_IadnRjMAenIcVDZ...@bt.com>, Richard Heathfield
<inv...@invalid.invalid> writes

>I think there are more important reasons not to like it, such as the
>incorrect use of ==, the mismatched parentheses, and (after those are
>corrected) the division by 0 which dumps core all over my shell.

Hey this was a homework question :-)

[Francis Glassborow]

In article <R8SdnfwSVZksk1PZ...@pipex.net>, Stuart Golodetz
<sgol...@dNiOaSl.PpAiMpPeLxE.AcSoEm> writes

>Why a vector rather than a list? Appending to a list would be faster surely?

No, I think not. A list requires memory allocation for every node. A
vector is designed to use amortised constant time and in addition only
allocates memory periodically. In fact I would probably assign enough
memory to start with.

[Stuart Golodetz]

"James Dennett" <jden...@acm.org> wrote in message
news:Bbpzg.12426$lv.10784@fed1read12...

Erm, I confess I didn't time it. I think I may have been talking rot again
actually...apologies. Is inserting at the end of a vector amortised constant
time (assuming a decent allocation strategy), thinking about it? In which
case the (amortised) cost of inserting at the end of either a vector or a
list would be O(1), making it definitely one to time to find out which would
be faster in practice. Sorry, wasn't thinking clearly before (may still not
be in practice...)

Cheers,
Stu

[Stuart Golodetz]

"Francis Glassborow" <fra...@robinton.demon.co.uk> wrote in message

news:ZX9pL0VX...@robinton.demon.co.uk...

> In article <R8SdnfwSVZksk1PZ...@pipex.net>, Stuart Golodetz
> <sgol...@dNiOaSl.PpAiMpPeLxE.AcSoEm> writes
>>Why a vector rather than a list? Appending to a list would be faster
>>surely?
>
> No, I think not. A list requires memory allocation for every node. A
> vector is designed to use amortised constant time and in addition only
> allocates memory periodically. In fact I would probably assign enough
> memory to start with.

Yes, sorry, I wasn't thinking straight. For some reason I'd temporarily
forgotten everything I ever knew about amortised analysis. My tutors would
not be pleased :)

Apologies, anyway,
Stu