Problem in Generating 1st 100 Primes

B

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 (e-mail address removed)

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
 
B

BigBrian

baltimoredude1 said:
> 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
 
K

Kai-Uwe Bux

baltimoredude1 said:
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 (e-mail address removed)

Thanks
A M Rahman

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

#include<iostream.h>

#include said:
#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.
 
V

Victor Bazarov

baltimoredude1 said:
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 (e-mail address removed)

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 said:
#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
 
M

Mark P

baltimoredude1 said:
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 (e-mail address removed)

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.
 
P

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
 
B

baltimoredude1

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

HMM... OUTPUT IS POSTED.. PLEASE DO THE COUNTING...
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....
A couple of things that I immediately see. Comments below...


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:



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

MAYBE YOU SHOULD DO SOME RESEARCH ON THIS ISSUE.
"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.
This should be

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


This should probably be simply

break;


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.
 
V

Victor Bazarov

baltimoredude1 said:
[..]
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...
 
G

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 ) );
}
..................
 
G

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 );
}
....
 
V

Victor Bazarov

Mark said:
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!
 
B

baltimoredude1

galeon said:
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++.
 
J

Jerry Coffin

[ ... ]
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.
 
V

Victor Bazarov

baltimoredude1 said:
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
 
B

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 said:
baltimoredude1 said:
HMM... OUTPUT IS POSTED.. PLEASE DO THE COUNTING...

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

[snip]
 
P

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,769
Messages
2,569,579
Members
45,053
Latest member
BrodieSola

Latest Threads

Top