Prime Numbers Test n/2 vs. sqrt(n)

[Moporho]

I have assignment and need help determining if I am correct. The question reads:
a.Write a function that determines whether a number is prime
b.use the function to determine and print out all prime numbers between 2 and 10,000. How many numbers to you have to test before being sure that you have found all primes?

c. You might think 2/n is the upper limit for the test, but you need to go as high as the square root of n. Why? Rewrite the program and estimate the performance improvement.

So the bold is the areas I need direction in.

First using 2/n

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <cmath>

#include<iomanip>
using std::setw;

bool prime(int n);

int main()
{
	int count = 0;

	cout << "The prime numbers from 2 to 10000 are:\n";

	for (int x =2; x <= 10000; ++x )

		if (prime(x)) 
		{
			++count;

			cout << setw( 6 ) << x;

					
		if ( count % 5 == 0)
			cout << endl;
	}
		cout << "\nThere were " << count << " prime numbers tested\n" << endl;

 return 0;
}
  bool prime (int n)
  {
  for ( int z = 2; (n/2) + 1 > z; z++ )

     if( n%z == 0 ) 
        return false;

   return true;
}

Second using sqrt(n)

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <cmath>

#include<iomanip>
using std::setw;

bool prime(int n);

int main()
{
	int count = 0;

	cout << "The prime numbers from 2 to 10000 are:\n";

	for (int x =2; x <= 10000; ++x )

		if (prime(x)) 
		{
			++count;

			cout << setw( 6 ) << x;

					
		if ( count % 5 == 0)
			cout << endl;
	}
		cout << "\nThere were " << count << " prime numbers tested\n" << endl;

 return 0;
}
  bool prime (int n)
  {
  for ( int z = 2; z<=sqrt(double(n)); z++)

     if( n%z == 0 ) 
        return false;

   return true;
}

So thoughts, comments, ideas??

M

[sarehu]

Why are you saying "2/n" when you mean "n/2"? For (b), I'd say you don't need to test any numbers for primality. For example, you don't need to test the even numbers, you don't need to test the multiples of three, etc. So I'm not sure what the teacher means by that. For (c), well, here's a hint: ask yourself, if N is divisible by K, where K > sqrt(N), what does that tell you about the value N/K?

[Moporho]

Sorry that was a quick typo!

I get that number is a Prime. The question eluding me is it faster? Did I eliminate numbers being tested by using sqrt()? I know I shortened up the process, but it just does not seem faster to me. I ran both. How do I find the number of numbers tested on each method?

M

[invisal]

Sorry that was a quick typo!

I get that number is a Prime. The question eluding me is it faster? Did I eliminate numbers being tested by using sqrt()? I know I shortened up the process, but it just does not seem faster to me. I ran both. How do I find the number of numbers tested on each method?

M

It is obvious already that sqrt() would be faster in most of the cases. Put it in this way, assuming that you want to check whether number 14,523 is prime number or not. By using n/2 way, your program would loop about 7,000 times. By using sqrt(), your program would loop only about 120 times.

[Moporho]

Exactly!

I think I am suppose to create a counter stating the times it goes through the loop using each function.

So I will eliminate the first counter because I do not need to see the number of primes between 2 and 10000. I do need to see how many loops execute as proof sqrt() eliminates the excess testing.

Am I close???? Comments Welcomed!
M

[Moporho]

It sounded like a plan in my head.

How do I count the loop executions. Everytime I try it I get errors.

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <cmath>

#include<iomanip>
using std::setw;

bool prime(int n);


int main()
{
	int count = 0;
	int counter=0;

	cout << "The prime numbers from 2 to 10000 are:\n\n";

	for (int x =2; x <= 10000; ++x )

		if (prime(x)) 
		{
			++count;

			cout << setw( 6 ) << x;

					
		if ( count % 5 == 0)
			cout << endl;
	}
		//cout << "\nThere were " << count << " prime numbers between 2 and 10,000\n" << endl;

 return 0;
}
int counter=0;
  bool prime (int n)
  {
	  
  for ( int z = 2; z<=sqrt(double(n)); z++) //testing sqrt() limit 
	   											
     if( n%z == 0 ) 

		 ++counter;
  cout << counter << endl;
		 
        return 0;

   return 1;
   
  
   }

[invisal]

Exactly!

I think I am suppose to create a counter stating the times it goes through the loop using each function.

So I will eliminate the first counter because I do not need to see the number of primes between 2 and 10000. I do need to see how many loops execute as proof sqrt() eliminates the excess testing.

Am I close???? Comments Welcomed!
M

Actually, creating the counter to count how many times you've looped is not so accurate. Since the sqrt(n) is processing slower than n/2. However, you can test which one is faster in the large testing by tracking the starting processing time to the ending processing time.

a = currect_time
proccessing_your_code
b = currect_time

In this way, you will know how many seconds does this code take to proccess and how many seconds does another code take to proccess. However, this method is still very accurate. The larger number of testing you do the more accurate it will be.

[VernonDozier]

Exactly!

I think I am suppose to create a counter stating the times it goes through the loop using each function.

So I will eliminate the first counter because I do not need to see the number of primes between 2 and 10000. I do need to see how many loops execute as proof sqrt() eliminates the excess testing.

Am I close???? Comments Welcomed!
M

I think you can cut down more here too if you'd like:

bool prime (int n)
  {
  for ( int z = 2; z<=sqrt(double(n)); z++)

     if( n%z == 0 ) 
        return false;

   return true;
}

If you keep track of what's prime and what is not prime as you go, you only have to make this calculation:

n % z

where z is a prime number. So say n is 17. The square root of n is 4.xxx, so you're testing numbers through 4. You don't need to test 4 since you know 4 is not prime already. Any number n where:

n % 4 == 0

will have already been ruled out as non-prime when you tested it against the number 2. So keep track of the primes you have calculated already. If a number z is not prime, skip it and move on. Saves you some calculations. You would however need to set up a boolean array to keep track of the prime numbers that you've already calculated.

[amitahlawat20]

I copied your code and executed it:
count =0 in the output.

You have used return 0 in your prime() method, so the if in main never receives value 1 and count is never incremented.

[vijayan121]

> but you need to go as high as the square root of n.
you need to test for divisibility only by *prime* numbers up to the root of n.
if you precompute and store all primes upto 100, testing if a number less than 10000 is prime would be even faster.

[Moporho]

How would that look? Do I need a storage class?

[Moporho]

VernonDozier,

I was good until the Boolean array. The next chapter in my class covers arrays. I am only up to Functions and Intro to Recursion.

invisal, I like the time thing and I will use it. Thanks.

vijayan121, What do you mean by 'but you need to go as high as the square root of n. ' ? I am confused as to how to store all primes too. I like how you say speed it up that is my main intent.

Thanks all,
M

[VernonDozier]

VernonDozier,

I was good until the Boolean array. The next chapter in my class covers arrays. I am only up to Functions and Intro to Recursion.

invisal, I like the time thing and I will use it. Thanks.

vijayan121, What do you mean by 'but you need to go as high as the square root of n. ' ? I am confused as to how to store all primes too. I like how you say speed it up that is my main intent.

Thanks all,
M

I imagine vijayan121 was thinking about an array as well, though I probably shouldn't put words in his mouth. Somehow you need to store the information of what's a prime and what isn't or you're losing what you've already calculated. I guess you could use a vector, but I imagine if you're not allowed to use an array, vectors are out too. If you are looking for efficient calculation times, I would stay away from recursion. Loops will serve you well here.

[Moporho]

Thank you all so much.

I'm leaning against putting a second counter to count the loop execution. Thoughts?

I really would like to use time but I am getting errors.

The programs seem to run correctly, but I feel I need to prove the change in speed. But how???

In the words of Scarlet O"Hara "I won't think about that now. I'll think about that tomorrow."

Thanks to all,
M

[vmanes]

One aspect not looked at in comparing the two functions (using n/2 or sqrt(n) as the loop limit) is the overhead of calling sqrt repeatedly, even if fewer times than the n/2 method loops.

To get the most out of that method, compute and store the sqrt(n) value before the loop begins, as in:

bool prime (int n)
  {
      double sq_root = sqrt( n );
      for ( int z = 2; z<= sq_root; z++)
          if( n%z == 0 ) 
               return false;

      return true;
}

Now from a clock timing perspective, you're really comparing apples to apples. And, you could also computer and store the n/2 value in that version. Now there's no question that it's just the number of loops that matter.

[vijayan121]

even if you do not have a store for all primes < 100 (you do need an array or vector for that), you can use the knowledge that even numbers greater than 2 are not prime. and cut the number of times through the loop by roughly half:

bool prime (int n)
  {
      if( n < 2 ) return false ; // all versions need this 
      if( n == 2 ) return true ;
      if( n%2 == 0 ) return false ;
      int root = sqrt( double(n) ) + 1 ;

      for ( int z = 3 ; z<= root; z += 2 )
          if( n%z == 0 ) return false;

      return true;
}

[monroe85]

#include <iostream>
using namespace std;



int main()
{


int w,x,y,z,avg;



cout <<" ENTER EACTLY FOUR INTEGER EXAM  MARKS"<<endl;
cout <<"I'L TELL YOU WHETHER YOU PASSED AND GIVE YOUR AVERAGE"<<endl;
cin >> w >> x >> y >> z;



avg=((w+x+y+z)/4);
if(avg>60){
cout <<"CONGRATULATIONS,YOU HAVE PASSED!WITH A GRADE OF "<<endl;


}


else{
cout<<"YOU FAIL"<<endl;


}
cout<<avg <<endl;


return 0;
}

please help im new in programing i want to use th y or y repeats.any other responses quits and i dont no how.

[vmanes]

Monroe,
a. You're hijacking the thread - asking a new, unrelated question that probably should be a new thread of its own.
b. Please read the sticky posts about how to ask a question and using BB tags around your code. And please format your code better - some indentation helps readability, avoid the excesses of blank lines (some are good, too many are not.)
c. Do you know how construct a while or do...while loop? That's what you need, if I understand your question.

[Sky Diploma]

Hello Everyone ., This is my first post in this forum.

However to get the prime numbers between 5 to 10000 you can do this

First you will need to check whether the number is divisible by 2.

bool prime(int x)
{
        If ((x%2)!=0) 
           {
              if((x%3)!=0)
               {
                   if ((x%5)!=0)
                      {
                      return x;
                       }
                }
             }
}

But it doesnt detect 2,3 and 5 as prime numbers as they are being used up.

Sorry My C++ is kinda poor. But not bad for a 16 year old new programmer. And i am sorry that i dint test the upper code

I hope i am correct ..

[VernonDozier]

Hello Everyone ., This is my first post in this forum.

However to get the prime numbers between 5 to 10000 you can do this

First you will need to check whether the number is divisible by 2.

bool prime(int x)
{
        If ((x%2)!=0) 
           {
              if((x%3)!=0)
               {
                   if ((x%5)!=0)
                      {
                      return x;
                       }
                }
             }
}

But it doesnt detect 2,3 and 5 as prime numbers as they are being used up.

Sorry My C++ is kinda poor. But not bad for a 16 year old new programmer. And i am sorry that i dint test the upper code

I hope i am correct ..

You are returning an integer in a boolean function. Sometimes you are returning nothing. What about a number like 49? That's prime according to your code.

[Moporho]

I love it! I now notice the quickness.

Now, How could I count the times the loop was executed in each version?

I must be placing the counter in the wrong place or not programming it to do exactly what I want it to do. I have the counter that goes throught the first loop.

I am going to keep trying to get the counter to work! Ughhh!!!

Thanks for all the great lessons, the responses have been brilliant.
M

[Moporho]

I am sitting here crying. I went by and read the assignment over and I am totally lost.

The directions read:

Write a program to solve:

a) Write a function that determines whether a number is prime.

b) Use this function in a program that determines and prints all the prime numbers between 1 and 10,000. How many of these 10,000 numbers do you really have to test before being sure that you have found all the primes?

c) Initially, you might think that n/2 is the upper limit for which you must test to see whether a number is prime, but you need only go as high as the square root of n. Why? Rewrite the program, and run it both ways. Estimate the performance improvement.

Make certain that you define a class and have data members and a constructor.

How do I estimate the performance??

I am now going to work on the class but I got to tell you I am lost.

Any suggestions?

M

[Sky Diploma]

You are returning an integer in a boolean function. Sometimes you are returning nothing. What about a number like 49? That's prime according to your code.

Thanks for the info i guess we will need to add in 7 also.

[VernonDozier]

Thanks for the info i guess we will need to add in 7 also.

Then you have the same problem with 121, which is 11 times 11. It will come back as prime after you add in the code to check for multiples of 7. Then to catch 121, you'd have to add code to catch multiples of 11, and then it wouldn't work for 169, which is 13 times 13, and so on. In order to catch all of the primes up to 10,000, you would have to hard code in all the primes less than 100 using your methodology. I forget how many that is, but it's probably more than you want to have to hard code into your program.

[VernonDozier]

I am sitting here crying. I went by and read the assignment over and I am totally lost.

The directions read:

Write a program to solve:

a) Write a function that determines whether a number is prime.

b) Use this function in a program that determines and prints all the prime numbers between 1 and 10,000. How many of these 10,000 numbers do you really have to test before being sure that you have found all the primes?

c) Initially, you might think that n/2 is the upper limit for which you must test to see whether a number is prime, but you need only go as high as the square root of n. Why? Rewrite the program, and run it both ways. Estimate the performance improvement.

Make certain that you define a class and have data members and a constructor.

How do I estimate the performance??

I am now going to work on the class but I got to tell you I am lost.

Any suggestions?

M

Well, maybe a class called "number", with four data members?

int value;         // 7 for number 7, 8 for number 8
bool isPrime;      // true for 7, false for 8
int performance1;  // however you decide to define
                   // efficiency for value/2
int performance2;  // however you decide to define
                   // efficiency for sqrt (value)

[Moporho]

Please Help?

This is what I have doen so far and I can not get the program to run. I keep getting many many errors. I have been working on this too long and I am not seeing what is happening. Please help with a fresh set of eyes...

First the class files .h

class number
{
public:
	void displayOn();
	void useDivisionFunction();
	void useSquareFunction();
private:
	
	
};

next the class resource file

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <cmath>
#include "number.h"

#include<iomanip>
using std::setw;


void number::displayOn(void)
{
	cout << "The prime numbers from 2 to 10000 are:\n\n";
	}


void useDivisionFunction()
{
	int count=0;
	bool prime (int x);

		for (int x = 2; x <= 10000; ++x )

		if (prime(x)) 
		{
			++count;

			cout << setw( 6 ) << x;

					
		if ( count % 5 == 0)
			cout << endl; 
			}
		
 return;
}
  bool prime (int n)
  {
  for ( int z = 2; (n/2) + 1 > z; z++ )

     if( n % z == 0 ) 

        return false;

   return true;
} // end useDivisionFunction

void useSquareFunction()
{
	int count=0;
	bool prime (int x);
	
	for (int x = 2; x <= 10000; ++x )

		if (prime(x)) 
		{
			++count;
			
			cout << setw( 6 ) << x;
					
		if ( count % 5 == 0)
			cout << endl;
	}
		cout << endl;
	
 return 1;
}
  bool prime (int n)
  {
	  if(n < 2)  

		  return false;

	  if(n == 2) 

		  return true;

	  if (n % 2 == 0) 

		  return false;

	  double root = sqrt(double(n))+ 1;


  for ( int z = 3; z <= root; z += 2)

	  if( n % z == 0 ) 
        
		 return false;

   return true;
   	  
} // end UseSquareFunction

and finally main

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <cmath>
#include "number.h"

#include<iomanip>
using std::setw;


void useDivisionFunction();
void useSquareFunction();

bool prime(int n);

int main()
{		
	
	number p;  // created number object

	p.displayOn(); // displays range
	p.useSquareFunction();
	p.useDivisionFunction();

	return 0;
}

It is a total mess.

What and where am I going wrong?

M

[VernonDozier]

// number.h
class number
{
public:
	void displayOn();
	void useDivisionFunction();
	void useSquareFunction();
private:
	// put data members here
	
};

Stick the following two lines at the top. It's a good habit to get into:

#ifndef NUMBER_H
#define NUMBER_H

At the bottom, put this:

#endif

You have your functions in the right place (public). You'll put your constructors there too. Data members are usually private. You'll usually have public "Get" and "Set" functions in the public section to access and change the data members. You may not need to worry about those for now. If you want to simplify life, you can make your data members public too (no need for "Get" and "Set" functions, but I imagine your professor wants them private and it's a good habit to get into).

// number.cpp
#include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <cmath>
#include "number.h"

#include<iomanip>
using std::setw;


void number::displayOn(void)
{
	cout << "The prime numbers from 2 to 10000 are:\n\n";
	}


void useDivisionFunction()
{
	int count=0;
	bool prime (int x);

		for (int x = 2; x <= 10000; ++x )

		if (prime(x)) 
		{
			++count;

			cout << setw( 6 ) << x;

					
		if ( count % 5 == 0)
			cout << endl; 
			}
		
 return;
}
  bool prime (int n)
  {
  for ( int z = 2; (n/2) + 1 > z; z++ )

     if( n % z == 0 ) 

        return false;

   return true;
} // end useDivisionFunction

void useSquareFunction()
{
	int count=0;
	bool prime (int x);
	
	for (int x = 2; x <= 10000; ++x )

		if (prime(x)) 
		{
			++count;
			
			cout << setw( 6 ) << x;
					
		if ( count % 5 == 0)
			cout << endl;
	}
		cout << endl;
	
 return 1;
}
  bool prime (int n)
  {
	  if(n < 2)  

		  return false;

	  if(n == 2) 

		  return true;

	  if (n % 2 == 0) 

		  return false;

	  double root = sqrt(double(n))+ 1;


  for ( int z = 3; z <= root; z += 2)

	  if( n % z == 0 ) 
        
		 return false;

   return true;
   	  
} // end UseSquareFunction

Line 14. You don't really need the "void" in the parentheses. If there are no arguments, just have empty parenthese like you do in line 20. Line 20 needs to be in the format that line 14 is in:

void number::useDivisionFunction()

Line 51 - see above comment. It needs the number:: in it if it's a class function.
Line 23: No clue what you are doing there but you don't want it there, so delete it. That is not a function call.
Line 69 - You're returning a value from a void function.

You have two "prime" functions?

Format your code so we can tell what brackets go with what. You could well have a brackets problem or a function within a function if the comment on line 96 is accurate.

//main.cpp
#include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <cmath>
#include "number.h"

#include<iomanip>
using std::setw;


void useDivisionFunction();
void useSquareFunction();

bool prime(int n);

int main()
{		
	
	number p;  // created number object

	p.displayOn(); // displays range
	p.useSquareFunction();
	p.useDivisionFunction();

	return 0;
}

Comment out everything but return 0 until you write at least one constructor.

[Moporho]

number.cpp

#include <iostream>
using std::cout;
using std::endl;

#include <cmath>
#include "number.h"

#include<iomanip>
using std::setw;

// constructor initializes PrimeNumberwith bool as arugment
number::number(bool prime) 
{
	setPrimeName(prime);

}// end function setPrimeNumber
}

bool number::getPrimeNumber()
{
	return prime;
}// end function getPrimeNumber

void number::displayOn()
{
	cout << "The prime numbers from 2 to 10000 are:\n\n";
	}


void number::useDivisionFunction()
{
	int count=0;
	
		for (int x = 2; x <= 10000; ++x )  //loop

		if (prime(x)) 
		{
			++count;

			cout << setw( 6 ) << x;

					
		if ( count % 5 == 0)
			cout << endl; 
			}
		
 return 0;
}
  bool prime (int n)
  {
  for ( int z = 2; (n/2) + 1 > z; z++ )

     if( n % z == 0 ) 

        return false;

   return true;
} // end useDivisionFunction

  void number::useSquareFunction()
{
	int count=0;
	bool prime (int x);
	
	for (int x = 2; x <= 10000; ++x )

		if (prime(x)) 
		{
			++count;
			
			cout << setw( 6 ) << x;
					
		if ( count % 5 == 0)
			cout << endl;
	}
		cout << endl;
	
 return 0;
}
  bool prime (int n)
  {
	  if(n < 2)  

		  return false;

	  if(n == 2) 

		  return true;

	  if (n % 2 == 0) 

		  return false;

	  double root = sqrt(double(n))+ 1;


  for ( int z = 3; z <= root; z += 2)

	  if( n % z == 0 ) 
        
		 return false;

   return true;
   	  
} // end UseSquareFunction

number.h

#ifndef NUMBER_H
#define NUMBER_H

class number
{
public:
	void displayOn();
	void useDivisionFunction();
	void useSquareFunction();
	void setprimeNumber(bool);
	bool getprimeNumber();
private:
	bool primeNumber; // data member 


	#endif
	
};

main

#include <iostream>
using std::cout;
using std::endl;

#include <cmath>
#include "number.h"

#include<iomanip>
using std::setw;

bool prime(int n);

int main()
{		
	
	number p;  // created number object

	p.displayOn(); // displays range
	p.useSquareFunction();
	p.useDivisionFunction();

	return 0;
}

It is just not working. I know I really screwed up with the constructor and the data members. Every thing is just escaping my brain now. This is due in less than two hours and I can not get the program to run at all.

Will I ever ever get C++????????

M

[Moporho]

You were right VernonDozer,
the Professor wants all data members to have set & get functions.

My class in online and unfortunately I did not know that my college did not have video lectures. All it is, is pay your tuiton, buy the book read and submit assignments.

What I learned so far I learned from using tutorials (internet) and the threads from these forums.

I am so so discouraged.

M

[VernonDozier]

You need to format your code so things line up and code inside brackets, loops, if statements, etc. is indented so it is readable by a human. The compiler doesn't care but others (and you) need to be able to read your code and it's much harder if the spacing is off like it is in yours. Most good IDEs have code formatting features that line things up with a click of a button.

For number.h, the #endif directive goes at the very end of the file, AFTER the semicolon that ends the class declaration.

You need to have at least a null constructor if you don't comment things out in main. This one will do for now. In the number.h file, add this function in the public section:

number ();

In number.cpp, add this function:

number::number ()
{
}

It doesn't do anything, but it's there. You have a constructor which takes a parameter in your .cpp file, but I don't see it in your .h file. Add this to your .h file:

number (bool prime);

I see at least one bracket problem in one of your files and I suspect there are more. You need to format your code. These bracket problems will stand out MUCH better if you do. Comment out all of your main program except for return 0. Don't uncomment it out till everything compiles and runs. You'll probably have to comment out a bunch more in your class too, particularly the functions you have implemented. Just give them meaningless return values (of the right type) till it compiles. After you get it to compile, uncomment the call to the constructor and see if that compiles, and work from there.