Prime number generator between two no's. Error-- time limit exceeded

Question

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 22-Sep-18 21:40pm

Prateek Krishna

Updated 9-Jun-20 9:08am

v2

Add a Solution

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;

3 solutions

Solution 1

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!

Posted 22-Sep-18 22:22pm

OriginalGriff

Solution 3

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.

Posted 23-Sep-18 5:04am

Dave Kreskowiak

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Patrice T · Accepted Answer · 2018-09-23T01:07:00

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.