I want to write a program that will print out prime numbers in order.
My program right now all it does is checking if the number is prime or not, and prints "1" for prime, "0" if it's not prime, and prints out instead of prime numbers, only 0's and 1's.
I have included <math.h> library, so why do I get the error for sqrt(n)?
#include <iostream>
#include <conio.h>
#include <math.h>
usingnamespace std;
int PrimeNumber(int);
int main()
{
int n;
cout<<"n="; cin>>n;
for(int i=0; i<n; i++)
cout<<PrimeNumber(i)<<" ";
_getch();
}
int PrimeNumber(int n)
{
for(int i=2;i<sqrt(n); i++) // error C2668: 'sqrt' :
// ambiguous call to overloaded function
if(n%i==0)
{
returnfalse; //If it isn't a prime number
}
returntrue; //If it is a prime number
}
You don't need to import a library for such a simple problem. If you can do some math, you'll see that i < √n is the same as i² < n. Therefore, your prime number function can look like this:
1 2 3 4 5 6 7
int PrimeNumber(int n)
{
for(int i = 2; i * i < n; i++)
if(n % i == 0)
returnfalse;
returntrue;
}
Also, check only odd numbers; every even number except for two is not prime.
This will cout prime number from 2 to 100. i hope this helps
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
#include <iostream>
usingnamespace std;
int main ()
{
int i, j;
for(i=2; i<100; i++) {
for(j=2; j <= (i/j); j++) {
if(!(i%j)) break; // if factor found, not prime
}
if(j > (i/j)) cout << i << " is prime\n";
}
return 0;
}
I would suggest a sieve of Eratosthenes. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes as it is trivial to implement and is fairily fast for what you are doing. Though if you want a lot like > 2 billion primes you should use a more efficient sieve.
#include <iostream>
#include <conio.h>
usingnamespace std;
int PrintPrime(int);
int main()
{
int n;
cout<<"n="; cin>>n;
for(int i=2; i<=n; i++)
cout<<PrintPrime(i)<<" "; // calling the function should print out the prime numbers
_getch();
}
int PrintPrime(int n)
{
int i, j;
for(i=2; i<=n; i++)
for(j=2; j<(i/j); j++)
{
if((i%j) == 0) break;
}
if(j>n)
return i;
}
int PrimeNumber(int);
int main()
{
int n;
cout<<"n="; cin>>n;
for(int i=2; i<n; i++)
if (PrimeNumber(i)==true)
cout<<i<<" ";
_getch();
}
int PrimeNumber(int n)
{
for( int i=2; i<n; i++) //for(int i=2;i<sqrt(double(n)); i++) , strange that it
// prints out numbers that are not prime
if(n%i==0)
{
returnfalse; //If it isn't a prime number
}
returntrue; //If it is a prime number
}
But still I don't understand why it doesn't show only primes when I use the divisors until sqrt(n), I also commented the code there.
Your last example there will compute sqrt(n) each time through the loop. It's better to do it once: Also, if you do a special purpose check for even numbers then you can skip them in the loop. To me, this is a nice trade off between a simple algorithm and fast runtime:
1 2 3
if (n%2 == 0) returnfalse; // it's even
int sqrtn = sqrt(double(n));
for (int i=3; i<sqrtn; i += 2)