what did i do wrong?

[jestermonkey92]

#include <iostream>
#include <conio.h>
#include <math.h>
using namespace std;
int n;
int i;
int b;
int main ()
{
cout << "enter a number and this program will" "\n" "list all of the primes up to that number" "\n";
cin >> n;
for ( int i = 1; i<= n; i++)
for ( int b = 2; b<= sqrt((static_cast<double>(i))); b++)
{
if (i % b == 0)
{cout<< i;
cout<< " is not prime";
cout<< "\n";}
else
{cout<< i;
cout<< " is prime";
cout<< "\n";}
}


getch();
return 0;
}


i know that it is a mostly useless program but im wondering why it sorta works and sorta doesnt
for example
if i input the number 15, it displays this
4 is not prime
5 is prime
6 is not prime
7 is prime
8 is not prime
9 is prime
9 is not prime
10 is not prime
10 is prime
11 is prime
11 is prime
12 is not prime
12 is not prime
13 is prime
13 is prime
14 is not prime
14 is prime
15 is prime
15 is not prime

why would it do that?

[Aakanaar]

I'm having a hard time reading that. could you please surround the code part with [code][/code] tags? Then indent the spacing as needed to make it easier to read. I think you might be missing some end curly braces, but i'm unsure.

[jestermonkey92]

i know that is isnt the braces
it runs but it doesnt seem to run correctly ie it says that 15 is prime then right after it says 15 is not prime. obiviously 15 is not a prime number so why would the computer think that it was?

[Aakanaar]

ok.. we'll look at the logic of the code. The primary function (the part we're interested in) is this section

for ( int i = 1; i<= n; i++)
  for ( int b = 2; b<= sqrt((static_cast<double>(i))); b++)
  {
    if (i % b == 0)
    {
      cout<< i;
      cout<< " is not prime";
      cout<< "\n";
    }

    else 
    {
      cout<< i;
      cout<< " is prime";
      cout<< "\n";
    }
  }

so, you have, for (b = 2; b <= sqrt((static_cast<double>(i))); b++)
I am no expert on this finding prime but am having a hard time figguring out why you need a square root..

if (i % b == 0) // if b devides into i evenly then it's not a prime
{...} // so we print it out

else // hrm, we havn't even bothered checking the rest of the b's yet.
{..} // so this print is pre-mature

What I might do differently is
for (b = 2; b < i; b++) // just make sure it's less than i

if (i % b == 0) // i liked this part
{ prime = false; } // just declare a bool named prime somewhere above
// and set it to true

then after looping through the b's.. if prime is still true, it's prime and print it. if not, it's not prime. reset prime to true, and move on to next iteration of the i loop.

[mahlerfive]

The reason you are missing some numbers and getting repeats of others is that you are printing inside the loop that is finding if the number has a factor. This is a problem because it could have many factors or no factors.

What you should probably do is write a simple function that takes a number and returns if it was prime (true or false). Then your main function can just have one loop that sends each number to the prime function, and prints out the result for each one.

The prime function can look something like this:

bool IsPrime( int num ) {
    // Code to determine if num is prime goes here, this will be similar to some of your current code, looking to see if it has a factor.
    // However 1 and 2 may be special cases
}

[jestermonkey92]

thanks ill try that
the sqrt is just to optimize the code a bit.

[helios]

Arkanaar: To naïvely check primality you don't need to test all numbers between 2 and n-1. Only all numbers between 2 and sqrt(n). Let's take the number 12 (~3.4641^2) for example:
You could check all numbers and find that it is divisible by 2, 3, 4, and 6. Notice that 2*6=12, but also 6*2=12. Also notice how the possible divisors seem to revolve around ~3.4641. If 12 wasn't divisible by 2, then it couldn't be divisible by 6, either. If it wasn't divisible by 3, it couldn't be divisible by 4, either. So once you've checked the divisibility of n by x<=sqrt(n), you've also checked it's divisibility by y>=sqrt(n).

jestermonkey92: You should not use functions from cmath (like pow(), sqrt(), sin(), cos(), tan(), etc.) inside loops if you intend to optimize. You should also avoid integer-floating point and floating point-integer conversions. Instead of doing b<=sqrt((static_cast<double>(i))), you could use b*b<=i. Alternatively, you could put before the loop int temp=sqrt((double)i);. That way, you wouldn't depend on compiler optimizations to have fast code.

[Aakanaar]

@helios
Ok. now that makes sense. I never knew that before. Thanks.

[jestermonkey92]

i have it corrected now.
thanks for all the help
i know that it still needs to be optimized, but it at least works correctly now.


#include <iostream>
#include <conio.h>
#include <math.h>
using namespace std;

//functions
int prime(int i);

//global varables
int num;
int i;

//main
int main()
{
int i;
cout << "enter a number ";
cin >> num;

for ( i = 2; i<= num; i++)
{
prime(i);
if (prime(i))
cout << i << " ";
}
getch();
return 0;
}

int prime(int i)
{
int j;
for (j = 2; j <= sqrt((double) i); j++)
{
if (i % j == 0)
return false;
}
return true;
}

[grecoman]

Well i thing this code can help you

#include <iostream>
#include <cstdlib>



using std::cout;
using std::cin;

int main ()
{
int n;
int m=0;
cout << "enter a number and this program will\n";
cout <<"list all of the primes up to that number" "\n";
cin >> n;
for ( int i = 1; i<= n; i++)
{
for (int b=1;b<=n;b++)

{
if (i % b == 0)
m+=1;



}
if(m<=2)
{
cout<<i<<"is prime \n";
}
else
{
cout<<i<<"is not prime \n";
}


m=0;

}



system("pause");
return 0;
}