Click here to Skip to main content
15,076,991 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:

we have to print prime numbers between two intervals m & n (m<=n<=1000000000) for t test cases(t<=10).
there may be some error in data types for m,n. but i have tried with long long too.

What I have tried:

#include <iostream>
using namespace std;

int main() {
	int m,n;
	int i,j,t;
	cin>>t;
	while(t>0)
	{
		cin>>m>>n;
		for(i=m;i<=n;i++)
		{ int p=1;
			for(j=2;j<=i/2;j++)
			{
				if(i%j==0)
				{
					p=0;
				}
			}
			if(p==1 && i!=1)
			{
				cout<<i<<"\n";
			}
		}
		cout<<"\n";
		t--;
	}
	return 0;
}
Posted
Updated 9-Jun-20 9:08am
v2
Comments
Richard MacCutchan 23-Sep-18 3:57am
   
You need to break out of the loop as soon as you identify that the number cannot be a prime. So replace p = 0; with break;

In addition to what Richard says, you have a very large range of numbers there - 1:1,000,000,000 is a big range - and you are doing probably 10 test cases.
And for every single number on that range, you repeat nested loops without any reference to previous solutions, using a modified Sieve algorithm. That's just not efficient, and I doubt that even improving it to run to the square root of the top number will improve it sufficiently.

Start reading: What's the best algorithm to check if a number is prime? - Quora[^] - there are other ways to do this, which may get you under your time limit. But you will almost certainly have to write code that is a lot more efficient than you have at the moment!
   
Quote:
time limit exceeded

Your problem is that your method is too slow, because it is overkill.
You stop checking factors at n/2, do you have a reason to stop there ?
Think about this:
What is the minimum multiple of 3 that is not a multiple of 2 ?
What is the minimum multiple of 5 that is not a multiple of 2 or 3 ?
What is the minimum multiple of 7 that is not a multiple of 2, 3 or 5 ?
For each of those numbers, what is their product of primes ?
The answers should lead you to a more efficient upper limit.

Once you know that 2 is not a factor, do you need to test factors 4, 6, 8, 10, 12 ... ?

Advice: Define a function IsPrime() which will check if an integer is a prime or not. It will separate concerns in your code.

We do not do your HomeWork.
   
Your current algorithm isn't going to make the time limit, no matter what you pick for bailout limits.

There are other ways of generating prime numbers that are FAR faster. I suggest you start with a few Google searches.
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900