Help on Prime Number problem!!

[mrrko]

I did all the coding, and I think that it is correct, but I dont understand why the program does not output the prime numbers!!!

#include<iostream>
using namespace std;
int main()

{
    double newn;
    char ans;

	do
	{
		cout << "This is a program that will help you find all the prime numbers between 3 and 100.\n";
		cout << "This numbers are: \n";
		
		for (int n = 3; n <= 100; n++)
		{
			for (int i = 2; n < i; ++i)
 	                {
                                newn = n % i;
				while(newn > 0)
				{ 
					cout << n << " ";	
				}
			}
		}
		cout << endl;

	cout << "Do you want to run this program again? Press 'Y' for yes, or 'N' for no\n";
	cin >> ans;

	} while (ans == 'Y' || ans == 'y');

	cout << "Have a nice day!\n";

	return 0;
}

What did I do wrong??? When I compile it and run it, this is what it says:

This is a program that will help you find all the prime numbers between 3 and 100.
This numbers are:

Do you want to run this program again? Press 'Y' for yes, or 'N' for no

And it does not output any number!!! Help PLZ!!

[Alex Edwards]

Hmm something looks fishy here...

for (int n = 3; n <= 100; n++)
		{
			for (int i = 2; n < i; ++i)
 	                {
                                newn = n % i;
				while(newn > 0)
				{ 
					cout << n << " ";	
				}
			}
		}

In the above chunk of code, it seems as if the n < i statement evaluates to be false so the loop never executes.

n is always 3 <= n <= 100, and i is initialized to 2 each time the nested for loop is evaluated, but n < i will always return false because of the range of n.

You'll have to modify your nested for loop to accommodate for this logic error. I'm no prime-number professional, but I can at least see the boolean error in your code.

[mrrko]

Thanks a lot, without a doubt that is my error...

But I tried n > i... and it give me an infinite loop... so now I dont know what to do

[VernonDozier]

Thanks a lot, without a doubt that is my error...

But I tried n > i... and it give me an infinite loop... so now I dont know what to do

Well what are you TRYING to do with this loop? Go through all the numbers greater than or equal to n, but less than or equal to 100 or something similar? Go through numbers that are less than n? I don't understand the algorithm.

[Alex Edwards]

Here's a solution, though it is not efficient at all.

#include <iostream>

using std::cin;
using std::cout;
using std::endl;
using std::ostream;

template< unsigned int max >
inline ostream& primeNumbers(ostream& out = cout){

    for(int i = 2; i <= max; i++){
        bool isPrime = true;
        for(int j = 2; j <= i; j++){
            if( ( (i%j) == 0) && (j != i))
                isPrime = false;

            if((j == i) && (isPrime == true))
                out << i << " ";
        }
    }
    return out;
}

int main(){

    primeNumbers<100>() << endl;
    cin.ignore();
    cin.get();
    return 0;
}

[mrrko]

Well what are you TRYING to do with this loop? Go through all the numbers greater than or equal to n, but less than or equal to 100 or something similar? Go through numbers that are less than n? I don't understand the algorithm.

To prove that the number is a prime number or not, I should divide it by every number from 2 to n-1... so if the number (in that case 3) should be divided by 2... if the number is 4, then it should be divided by 2 and 3... that's why it is used in the loop the "i is less than n"

[mrrko]

Here's a solution, though it is not efficient at all.

#include <iostream>

using std::cin;
using std::cout;
using std::endl;
using std::ostream;

template< unsigned int max >
inline ostream& primeNumbers(ostream& out = cout){

    for(int i = 2; i <= max; i++){
        bool isPrime = true;
        for(int j = 2; j <= i; j++){
            if( ( (i%j) == 0) && (j != i))
                isPrime = false;

            if((j == i) && (isPrime == true))
                out << i << " ";
        }
    }
    return out;
}

int main(){

    primeNumbers<100>() << endl;
    cin.ignore();
    cin.get();
    return 0;
}

Thanks men, but that is a little too complicated to what they have showed us in the class

[Alex Edwards]

The idea is simple enough...

For numbers 2- max, check the numbers between any one of these numbers...

If any number between the chosen number is a potential divisor of the number (and it isn't 1, nor the number itself) then the chosen number is not a prime number.

If no divisor can be found between 1 and the actual number, then it is a prime number.

I'm sure there is a better way of finding prime numbers than that approach. In fact, any time you have to use 2 for loops to solve a linear problem something is definitely wrong...

[emotionalone]

I was able to come up with this

#include<iostream>

using namespace std;

int main()
{
  double newn;
  char ans;
  do
  {
    cout << "This is a program that will help you find all the prime numbers between 3 and 100." << endl;
    cout << "Theses numbers are: " << endl;
    for (int n = 3; n <= 100; n++)
    {
      newn = 1;
      for (int i = n-1; i>=2 && newn ; i--)
        newn = n%i;
      if ( newn != 0 )
          cout << n << " ";
    }
    cout << endl;
    cout << "Do you want to run this program again? Press 'Y' for yes, or 'N' for no\n";
    cin >> ans;
  }
  while (ans == 'Y' || ans == 'y');
  cout << "Have a nice day!\n";
  return 0;
};

A number is a prime number if there are no exact divisions between that number and 2, excluding the number and 2. So I had newn start with a 1 so it would make the for() condition true from the start. I have newn as a condition in the for because we don't want to do more processes than we need to, if it's an exact division, then it's not a prime number and the loop stops.

[minigweek]

Hello,

first a tip.

TO check whether a number 'n' is prime or not, it is just enuff to check whether n is divisible by any integer from 2 to n/2 . no need to loop till n-1.
As you will observe, for say a number 24, obviously no number greater than 12 can divide it. And that is true for all integers.

next, your code snippe ::

for (int n = 3; n <= 100; n++)
		{
			for (int i = 2; n < i; ++i)
 	                {
                                newn = n % i;
				while(newn > 0)
				{ 
					cout << n << " ";	
				}
			}
		}

if changed to

int flag=1;
for (int n = 3; n <= 100; n++)
		{
			for (int i = 2;i<= n/2; ++i)
 	                {
                                newn = n % i;
                                if(newn==0)
                                {
                                   flag=0;
                                   break;
                                 }
				
		    }
                               if (flag==1)
                             {
                              cout<<" "<<n;
                              }
                              flag=1;
		}

The changes i made are ::
1. loop i from 2 till n/2
2. variable int flag.
-> set this to 1 at first , if none of the division gives a remainder 0, then it remains 1, meaning the number checked ( i ) is prime. else set it to 0 and break from inner loop.

it shud work.
regards

[emotionalone]

TO check whether a number 'n' is prime or not, it is just enuff to check whether n is divisible by any integer from 2 to n/2 . no need to loop till n-1.

A VERY good point. =) Thanks for the tip.

[VernonDozier]

Hello,
TO check whether a number 'n' is prime or not, it is just enuff to check whether n is divisible by any integer from 2 to n/2 . no need to loop till n-1.
As you will observe, for say a number 24, obviously no number greater than 12 can divide it. And that is true for all integers.

You actually only have to check up to the square root of n. Thus if you are testing, say, 97 for primality, the square root of 97 is 9.85, so if 97 is not prime, it must be divisible by an integer less than or equal to 9 (9.85 rounded down).