Problem in Generating 1st 100 Primes

[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 ba************@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

[BigBrian]

baltimoredude1 wrote:

int prime(int number)
{

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

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

This will return true when 'number' mod some number is not 0. 15 mod 2
is not zero ( so your function returns true ), but 15 is not prime.
Basically this prime function isn't implemented right.

-Brian

[Victor Bazarov]

baltimoredude1 wrote:

I was writing a simple code to generate the first 100 prime numbers.

Are you sure about "100"? You seem to only print out first 99, no?

Everything looks fine to me except the output of the program.

LOL... So, everything is OK, only it doesn't work, eh? That means
not everything is OK.

What's
wrong with it?

A couple of things that I immediately see. Comments below...

I am attaching the program as well as the output. Would
appreciate if someone could mail me at ba************@gmail.com

Thanks
A M Rahman

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

#include<iostream.h>

There is no such standard header. There hasn't been for as long as we had
the Standard. Why are you still writing non-standard code? Should be:

#include <iostream>

#include<process.h>

This is a non-standard header. Are you using anything from it, actually?

>
int prime(int number);
int main(void)

"void" between parentheses doesn't make much sense, unless you're writing
a C program. You're not. So, it doesn't. And although it's allowed, you
should take a habit of not using it.

{

int counter = 0;

for (int n = 2; n < 1000; n++)
{
if ( prime(n) == 1 )
{
cout << n << " ";

This should be

std::cout << n << " ";

counter ++;
if (counter 99)
{
exit(0);

This should probably be simply

break;

}

} // 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;

If there is a remainder from division, shouldn't you be going on trying
to find another divisor?

}

else
{
return 0;
}
} // close for

And once you checked _all_ numbers, what do you return?

}

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

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

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Kai-Uwe Bux]

baltimoredude1 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 ba************@gmail.com

Thanks
A M Rahman

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

#include<iostream.h>

#include <iostream>

#include<process.h>

Not a standard header. Not used anyway.

int prime(int number);

May I recommend

bool is_prime( unsigned 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
}

Note:

a) This function never returns a value for number == 2. Thus, you have
undefined behavior in main().

b) For number 2, the prime() function is semantically broken. The for loop
never enters the second iteration, i.e., i==2 is the only case that ever
occurs: if number is not a multiple of 2, prime returns 1, if number is a
multiple of 2, prime returns 0. This matches the output.

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

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

[Mark P]

baltimoredude1 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 ba************@gmail.com

It's pretty obvious what's wrong with the output-- you've printed out
every odd number greater than 2.

>
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

Time for lesson 1 of debugging. Step through the code! Pick a value
where you're getting the wrong result and see what happens. We know 9
isn't a prime so put 9 into your function and watch what it does. When
it says 9 *is* a prime figure out what must be wrong with your logic.

int prime(int number)
{

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

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

Here's a hint: For a single call to prime() what's the most number of
times that the for loop can run? Remember that the function (and hence
the loop) will end as soon as a return is encountered.

>
-----------------------------------------------------------------------------------------------------------------------------------//

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

[Panks]

Hi

Your prime function should be like below : -

int prime(int number)
{

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

} // close for

return 1;

}

I hope this willl solve your problem

Pankaj

[baltimoredude1]

Victor Bazarov wrote:

baltimoredude1 wrote:

I was writing a simple code to generate the first 100 prime numbers.

Are you sure about "100"? You seem to only print out first 99, no?

HMM... OUTPUT IS POSTED.. PLEASE DO THE COUNTING...

>

Everything looks fine to me except the output of the program.

LOL... So, everything is OK, only it doesn't work, eh? That means
not everything is OK.

LOOKS OK TO ME AND I KNOW IT'S NOT OK....

>

What's
wrong with it?

A couple of things that I immediately see. Comments below...

I am attaching the program as well as the output. Would
appreciate if someone could mail me at ba************@gmail.com

Thanks
A M Rahman

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

#include<iostream.h>

There is no such standard header. There hasn't been for as long as we had
the Standard. Why are you still writing non-standard code? Should be:

#include <iostream>

#include<process.h>

This is a non-standard header. Are you using anything from it, actually?

MAYBE YOU SHOULD DO SOME RESEARCH ON THIS ISSUE.

>

int prime(int number);
int main(void)

"void" between parentheses doesn't make much sense, unless you're writing
a C program. You're not. So, it doesn't. And although it's allowed, you
should take a habit of not using it.

AGAIN DO SOME RESEARCH ON THIS ISSUE.

>

{

int counter = 0;

for (int n = 2; n < 1000; n++)
{
if ( prime(n) == 1 )
{
cout << n << " ";

This should be

std::cout << n << " ";

counter ++;
if (counter 99)
{
exit(0);

This should probably be simply

break;

}

} // 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;

If there is a remainder from division, shouldn't you be going on trying
to find another divisor?

ANYWAY I FIGURED OUT THE PROBLEM AND IT'S WORKING FINE.

>

}

else
{
return 0;
}
} // close for

And once you checked _all_ numbers, what do you return?

}

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

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

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[baltimoredude1]

I figured it out and it's working fine

Panks wrote:

Hi

Your prime function should be like below : -

int prime(int number)
{

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

} // close for

return 1;

}

I hope this willl solve your problem

Pankaj

[Victor Bazarov]

baltimoredude1 wrote:

[..]
HMM... OUTPUT IS POSTED.. PLEASE DO THE COUNTING...
[..]
LOOKS OK TO ME AND I KNOW IT'S NOT OK....
[..]
MAYBE YOU SHOULD DO SOME RESEARCH ON THIS ISSUE.
[..]
AGAIN DO SOME RESEARCH ON THIS ISSUE.
[..]
ANYWAY I FIGURED OUT THE PROBLEM AND IT'S WORKING FINE.

For a netiquette violator, you're being too polite. You need
to call me an ass or something. To complete the picture...

[galeon]

I guess it's more efficient!
...................
bool is_Prime( unsigned candidate )
{
if ( candidate == 2 )
return ( true );
int lim = sqrt( ( double )candidate );
for ( int index = 3; index <= lim; index += 2 )
if ( candidate % index == 0 )
return ( false );
return ( ( candidate % 2 ) );
}
..................

[galeon]

This is better...
....
bool is_Prime( unsigned candidate )
{
if ( candidate < 2 )
return ( false );
int lim = sqrt( ( double )candidate );
for ( int index = 3; index <= lim; index += 2 )
if ( candidate % index == 0 )
return ( false );
return ( true );
}
....

[Mark P]

baltimoredude1 wrote:

Victor Bazarov wrote:

>baltimoredude1 wrote:

>>I was writing a simple code to generate the first 100 prime numbers.

Are you sure about "100"? You seem to only print out first 99, no?

HMM... OUTPUT IS POSTED.. PLEASE DO THE COUNTING...

Even though he's clearly a moron, he does actually have you on this point.

[snip]

>>-----------------------------------------------------------------------------------------------------------------------------------//

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

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Victor Bazarov]

Mark P wrote:

baltimoredude1 wrote:

>Victor Bazarov wrote:

>>baltimoredude1 wrote:
I was writing a simple code to generate the first 100 prime
numbers.
Are you sure about "100"? You seem to only print out first 99, no?

HMM... OUTPUT IS POSTED.. PLEASE DO THE COUNTING...

Even though he's clearly a moron, he does actually have you on this
point.

Aw... You got me! You all got me! Aw... I feel so dumb now... Aw..
How am I going to look my colleagues in the eyes after this... I will
have to quit my job, leave my home, and join the army or something...

So, you all can count and I can't. Good. We know another one of my
countless flaws. And why do you think I call them "countless"? Get it?
I can't count!

[baltimoredude1]

galeon wrote:

This is better...
...
bool is_Prime( unsigned candidate )
{
if ( candidate < 2 )
return ( false );
int lim = sqrt( ( double )candidate );
for ( int index = 3; index <= lim; index += 2 )
if ( candidate % index == 0 )
return ( false );
return ( true );
}
...

Why are you square rooting it and increasing the index by 2? I have
rectified the code and it's working though your version looks a bit
more sophisticared. It might sound silly but I am trying to learn C++
all by myself so sometimes you may have to bear with me. Infact I am a
novice and is using an older version of Borland C++.

[Victor Bazarov]

baltimoredude1 wrote:

galeon wrote:

>This is better...
...
bool is_Prime( unsigned candidate )
{
if ( candidate < 2 )
return ( false );
int lim = sqrt( ( double )candidate );
for ( int index = 3; index <= lim; index += 2 )
if ( candidate % index == 0 )
return ( false );
return ( true );
}
...

Why are you square rooting it and increasing the index by 2? I have
rectified the code and it's working though your version looks a bit
more sophisticared. It might sound silly but I am trying to learn C++
all by myself so sometimes you may have to bear with me. Infact I am
a novice and is using an older version of Borland C++.

Going beyond a square root of the number in search of divisors is a waste
of time: if there are divisors there (in the "upper" part), its pair has
already been encountered in the "lower" part.

Increasing the index by 2 makes sure you only check the odd numbers. If
you find a divisor that is even, then '2' must have already been found
as a divisor, and then the number isn't prime already.

The only thing missing here is actually checking for evenness, I guess.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[baltimoredude1]

Mark the counter is set at zero and ends at 99 which sums upto 100.
There are 100 numbers in the output.

Yeah I agree he is an idiot. He is the type of guys who thinks of
knowing everything but just not knowing the basic thing. You know the
guy who in class would ask the most stupid question to a professor
thinking that's the smartest thing to do. Yeah best thing to do is
ignore him.

Mark P wrote:

baltimoredude1 wrote:

Victor Bazarov wrote:

baltimoredude1 wrote:
I was writing a simple code to generate the first 100 prime numbers.
Are you sure about "100"? You seem to only print out first 99, no?

HMM... OUTPUT IS POSTED.. PLEASE DO THE COUNTING...

Even though he's clearly a moron, he does actually have you on this point.

[snip]

>-----------------------------------------------------------------------------------------------------------------------------------//

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
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Jerry Coffin]

In article <11**********************@75g2000cwc.googlegroups. com>,
ba************@gmail.com says...

[ ... ]

Why are you square rooting it and increasing the index by 2? I have
rectified the code and it's working though your version looks a bit
more sophisticared. It might sound silly but I am trying to learn C++
all by myself so sometimes you may have to bear with me. Infact I am a
novice and is using an older version of Borland C++.

The square root is because factors come in pairs, and if one factor
is larger than the square root, the other must be smaller than the
square root. IOW, if you reach the square root without finding any
factors, then there aren't any factors.

Adding two is because the code has already shown that the number
isn't a multiple of 2 -- and if it's not a multiple of 2, it can't be
a multiple of any even number, so after eliminating 2, you only need
to check against odd numbers.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[baltimoredude1]

Mark

I think it's also compiler oriented. Reason I also posted it on
alt.comp.lang.learn.c-c++ and someone ran it in Dev C and his output
ended at 201.

http://groups.google.com/group/alt.c...6eb5318e11d6c8
Mark P wrote:

baltimoredude1 wrote:

Victor Bazarov wrote:

baltimoredude1 wrote:
I was writing a simple code to generate the first 100 prime numbers.
Are you sure about "100"? You seem to only print out first 99, no?

HMM... OUTPUT IS POSTED.. PLEASE DO THE COUNTING...

Even though he's clearly a moron, he does actually have you on this point.

[snip]

>-----------------------------------------------------------------------------------------------------------------------------------//

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
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Panks]

Hi Galeon
Extremly beautifull logic we cud make it more efficient if loops runs
two ways

i meaning first find lim/2 the loop runs lim/2 times and we put two
checks one from beginig and other for after lim/2.
What do you say?

Pankaj