Prime numbers in a range

[Tej Samra]

Finding how many prime numbers are in a range given by the user

int num1;
int num2;

int numofvalues=0;
 cout << "Enter starting number:";
 cin >> num1;
 cout<< "Enter ending number";
 cin >>num2;
 

for(int start = num1; start<=num2; start++)
 
{
      
       
    if(start%2==0) 
        {
        numofvalues++;
        }

}

cout << numofvalues << endl;


 system("PAUSE");
 return(0);

}

it doesnt work for numbers like 15 and 21 because they are also divisible by 3.

[thechad90000]

I'm assuming numofvalues is supposed to hold the number of prime numbers within the range. That's fine but what you've got is if a number is evenly divisible by two, then add one to numofvalues. If it's evenly divisible by two then it's not prime.

You should have something that accounts for 2, 3, 5, 7 being prime and then also you should increment numofvalues for anything that isn't evenly divisible by those four values

[Tej Samra]

I tried doing if((start%2==0) || (start%3==0)) because that should work for most numbers. But the output is still wrong

from what your saying i should write it as (start%2!=0) but that adds numbers like 15 which arent prime. Do i need 2 for loops?

[Volatile Pulse]

Tej Semra wrote:

Tej Samra (16) Jun 10, 2012 at 11:54pm
I tried doing if((start%2==0) || (start%3==0)) because that should work for most numbers. But the output is still wrong

How is the output wrong? That should work for 15 and 21, but what in the case of 49? Then you don't test for 7. What about 121? you don't test for 11. What about 169, you don't test for 13.

You should make a vector that dynamically adds a prime number when your for loop finds one. Use the numbers stored in the vector to see if another number is prime, if the number is prime, add it to your vector.

[Tej Samra]

int num1;
int num2;
int start;
int numofvalues=0;

 
 cout << "Enter starting number:";
 cin >> num1;
 cout<< "Enter ending number";
 cin >>num2;
 

for(int i =2; i<start; i++)
{
for( start = num1; start<=num2; start++)
 
{
      
       
    if(start%i!=0)
        {
       
       numofvalues++;
    
        }

}
}


cout << "Number of primes in range:" << numofvalues << endl;





 system("PAUSE");
 return(0);

}

Been working on this problem all day... still wrong output. Can someone ease me by telling me im on the right track...

[TheSonsOfKings]

Pass your variables to the function before calling it.

[Tej Samra]

what do you mean?

[Bonii]

@Tej Samra:
There are quite a few different ways to compute primes. For the purpose of learning codes, unless you know a lot about number theory, in my opinion, "test-and-list" and the sieve of Eratosthenes are most beneficial. These are very simple algorithms, albeit quite unoptimized. How you implement them is up to you.

"Test-and-list" works by using the definition of prime numbers: a natural number (1,2,3...) is a prime number if every number (unless it is 1) smaller than it does not divide it. To test divisibility, you only need to test if smaller primes divide it. So the algorithm goes like this:
1) Read upper bound, say $U$.
2) Make an empty array, say $P$, (of some length depending on $U$) to store primes.
3) Set $n = 2$.
4) Test if any number in the array $P$ divides $n$. (In the case of empty array, no number in $P$ divides $n$. So test is negative.)
5) If there is a number in $P$ that divides $n$ (a positive result), go to (7).
6) If the test is negative, then $n$ is a prime. Add $n$ into the array $P$.
7) Increase $n$, and exit if it exceeds bound $U$. Go to (4) otherwise.
Because this uses some form of division, this is very processor intensive. But uses relatively less memory than the second method.

Sieve of Eratosthenes.. It might be better if you Wiki this. But basically, instead of trial by division, it removes every multiples of numbers in a list. The numbers that are not removed are then prime numbers. This requires you to store the "prime" status of every number you want to know about, therefore it can use up a lot of memory. But no multiplication or division is needed. (Again, this depends on your implementation.)

Bonii

[Shinigami]

First: make a function to find if given number is prime or not.
Second: make a function which use first function to see if number in range is prime or not, if it is prime increases numofvalues variable.
It should be easier to test and find bugs.

Or search this forum, here are hundreds of topics about it.

[Tej Samra]

@ shinigam

Not sure what you mean by function. I think I already have written a program to find primes by themselves in my last post. That method doesnt work for this. Can you show me what you mean in code using my code as a template.

[Shinigami]

By function I mean function. As you said you written a program, but not a function.
Function is a piece of program which do some work, mostly one work only. For example to find if number is prime.
Like this:

bool is_prime(const int & number)
{
	if (number < 2)
	{
		return false;
	}

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

second function use first function and prints all prime numbers.

void print_primes(int & number_1, const int & number_2)
{
	while (number_1 < number_2)
	{
		if (is_prime(number_1))
		{
			cout << number_1 << ", ";
		}
		number_1++;
	}
	
	return;
}

You can have even the third function for data input

void prime_range()
{
	int number_1, number_2;
	
	cout << "Enter first number: ";
	cin >> number_1;
	
	cout << "Enter second number: ";
	cin >> number_2;
	cout << endl;
	
	cout << "This is prime number: " << endl;
	print_primes(number_1, number_2);
	cout << endl;
	
	return;
}

And in main function is only this

int main()
{
	while (true)
	{
		prime_range();
		cout << endl;
	}
	return 0;
}

Like this it is easer to find errors by testing if one peace of program works or not.