finding prime numbers in C++

[MadSkillzMan]

ok i was never any good at math. But i have to write a program that will display the number of prime numbers between 2 integers. for example:

Enter the starting number: 50
Enter the finishing number: 59

Number of prime numbers in range: 2

ive been starin at similar problems all week...is there something non-prime numbers have in common? i dont need the entire program just a little help ...thanx

 

[Cowboy Shane]

Disclaimer: I really tried to do better this time about giving away the entire answer, but I think I may have said too much. Sorry, I am trying to leave something to the imagination.

Thoughts: You could brute force it by writing a boolean function to test each number in the range given to see if it is prime or not, and then just count the number of trues you get while progressing through the numbers. Something like

for(int i=low; i<=high; i++)
   if IsPrime(i)
      NumPrimes++;

To check if a number is prime, you use the modulus operator to check each integer from 2 to the square root of the number you are checking to see if it is evenly divisible. Something like "if (test%count = 0)".

 

[Cowboy Shane]

Again, I am not trying to do your homework, just trying to help. I'll make you translate it from Pascal

You could make the prime checking function a little more efficient with something like (not C++ syntax):

result := True;

//2 is prime
if TestNum = 2 then
  result := True
//Go ahead and get rid of multiples of 2, and any obvious non-primes
else if (TestNum < 2) or ((TestNum mod 2) = 0) then
  result := False
//Just check odd numbers
else begin
  ii := 3;
  while (ii <= sqrt(TestNum)) and (result) do begin
     if (TestNum mod ii) = 0 then
       result := False;
     ii := ii + 2; 
   end;
end;

 

[JigPu]

Yup, Cowboy Shane's first loop is exactly what you're looking for. So long as you know how to write a procedure to determine if a number is prime (just test if the number is evenly divisible by anything with modulo) you're gold

JigPu

 

[Crowley16]

Actually, if u need to check if a number is prime or not, u don't need to divide by every interger below the sqrt.
Just by the primes that's smaller than number/2.

if any of them returns a remainder of 0, then it's not a prime number.
(well, apart from 1, does 1 count as a prime?, god this takes me back...)

 

[Cowboy Shane]

That's assuming that you have a list of primes available to the program. If that were the case, then you would not need to divide at all, just list the primes that are between the two numbers.

For a simple program, brute forcing is probably the best method. There are more sophisticated methods for determing if a number is compoiste or prime, but they are probably well beyond the scope of an introductory programming class.

 

[mccoyn]

You could always write a recursive function. In order to find the primes in a range of numbers, you will need to know all the primes up to the square root of that number (crowley's method). So just call the function for the range (2, sqrt(max)), unless max is 2 or less, then its trivial.

 

[Crowley16]

yes, I was originally thinking of using a recursion method, but once I started to think about it I realised that to bring in recursion would be WAY beyond the scope of this piece of homework...

Yeah, the simplest way is to brute force it, but IF he does want to do some extra optimisation then he can use recursion with prime divisors.

It's kinda just an aside really, more about maths than C++

 

[JigPu]

Just by the primes that's smaller than number/2.

Almost Just by the primes <= number^0.5.

If you're going through the trouble of keeping a list of primes, don't waste the CPU cycles checking all the numbers up to X/2. At 1 Million you'd be doing mod on about 41,500 numbers, but if you only check to the square root you shave that down to a mere 150ish If a number dosen't divide by it's square root (regardless of if dividing by primes or integers), it's never going to.

JigPu

 

[MadSkillzMan]

ok ive been working at this in class all week and i cant figure it out at all...if i do 2 loops it freezes.....this is the closest ive got and it ALWAYS says 0 for the problem wer supposed to test it w....the problem is how many primes between 50 and 59? and the answer is 2...this ALWAYS says 0...but if i go 51 and 59 itll tell me like 4....so what am i doing wrong here?:

code:

#include<iostream.h>
int main()
{
int number;//Starting number
int x=2; //Counting mod number
int y=0; //flag number
int num=0; //second flag number

int finish; // Second number user enters
int stop=(finish-1);
cout<<"Please enter a number: ";
cin>>number;
cout<<"Enter a finishing number";
cin>>finish;

do{
if(number%x==0){
y++;
if (y==0)
num++;
}
if (x==finish-1)
x=2;
else if (x<finish-1)
x++;
number++;

}while (number<finish);
cout<<"There are "<<num<<" prime numbers in range";
return(0);
}

 

[Cowboy Shane]

Using the code tag to preserve the indentation:

    if(number%x==0)
    {
      y++;
      if (y==0)
        num++;
    }

That's the only place that num is incremented, and it can never happen. I'm not really sure what you are trying to do with that segment of code, but you can just use nested loops:

bool prime = true;
int i = 2;
while (number < finish)
  {
  while (prime && i<=sqrt(number))  
    {
    if ((number % i) == 0)
      prime = false;
    i++;
    }

  i = 2;
  if (prime)
    num++;
  
  //need to reset prime... forgot this at first
  prime = true;
  number++;
  }

 

[mccoyn]

ok ive been working at this in class all week and i cant figure it out at all...if i do 2 loops it freezes.....this is the closest ive got and it ALWAYS says 0 for the problem wer supposed to test it w....the problem is how many primes between 50 and 59? and the answer is 2...this ALWAYS says 0...but if i go 51 and 59 itll tell me like 4....so what am i doing wrong here?:

code:

#include<iostream.h>
int main()
{
int number;//Starting number
int x=2; //Counting mod number
int y=0; //flag number
int num=0; //second flag number

int finish; // Second number user enters
int stop=(finish-1);
cout<<"Please enter a number: ";
cin>>number;
cout<<"Enter a finishing number";
cin>>finish;

do{
if(number%x==0){
y++;
if (y==0)
num++;
}
if (x==finish-1)
x=2;
else if (x<finish-1)
x++;
number++;

}while (number<finish);
cout<<"There are "<<num<<" prime numbers in range";
return(0);
}

You are incrementing number every time. You should only be incrementing it when you reset x. So, the end of the loop should look like this:

do{
	.....

	if (x==finish-1){
		x=2;
		number++;
	} else if (x<finish-1) {
		x++;
	}
} while (number <= finish);

 

[Cowboy Shane]

Judging from your answer, I assume you need to include the boundary numbers (I tested this, so don't look if you don't want a complete solution):

#include <iostream>
#include <cmath>

int main()
{
  int LowNum = 0;
  int HighNum = 0;
  int Divisor = 2;
  int NumPrimes = 0;
  bool prime = true;
  
  std::cout << "Enter the first number:\n";
  std::cin >> LowNum;
  std::cout << "Enter the high number:\n";
  std::cin >> HighNum;
    
  while (LowNum <= HighNum)
  {
    while (prime && Divisor <= sqrt(LowNum))
    {
      if ((LowNum % Divisor) == 0)
        prime = false;
      
      Divisor++;
    }
    
    if (prime)
      NumPrimes++;
    
    Divisor = 2;
    prime = true;
    LowNum++;
  }
  
  std::cout << "There were " << NumPrimes << " prime numbers\n";
  
  return 0;
}

 

[Crowley16]

If you ever need to optimise it, then u could just use an list/vector to store the prime numbers that you've already worked out, and use them as the divisors.
That'll cut your loops by about 70% (<--guesstimate)...

something along the lines of: (psudo code)

   divisor = 2

   while divisor < sqrt(largeNumber)      
      for each prime in primes[]
         if divisor % prime == 0
            divisor not prime
            next divisor
         endif
      end for

      if divisor is prime
         add divisor to primes[]
      endif

      divisor += 1
   loop

this code is nowhere near C++ and nowhere near complete cos I'm far too lazy to give the full solution. But if anyone ever wants to optimise it, this is a simple thing to do that'll drastically cut the amount of calcs needed...

I think...

 

[mccoyn]

I have a pretty well optimized code here. It goes a step further, instead of checking every number against every prime it creates a vector element for each number, then filters them out for each prime. It works a lot faster because, for example 11 only has to be compared with 1 out of 11 numbers instead of comparing it with all of them the other way. Also I avoid using a slow modulus function and instead use addition.