Prateek Krishna Ответов: 3

Генератор простых чисел между двумя нет. Ошибка-- превышен лимит времени


мы должны вывести простые числа между двумя интервалами m & n (m<=n<=1000000000) для t тестовых случаев(t<=10).
там может быть какая-то ошибка в типах данных для m,n. но я тоже пробовал с long long.

Что я уже пробовал:

#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;
}

Richard MacCutchan

Вам нужно вырваться из петли, как только вы обнаружите, что число не может быть простым. Так что замените p = 0; с break;

3 Ответов

Рейтинг:
2

Dave Kreskowiak

Ваш текущий алгоритм не собирается устанавливать лимит времени, независимо от того, что вы выберете для лимитов спасения.

Есть и другие способы получения простых чисел, которые намного быстрее. Я предлагаю вам начать с нескольких поисков в Google.

Рейтинг:
14

Patrice T

Цитата:
превышен лимит времени

Ваша проблема в том, что ваш метод слишком медленный, потому что он излишен.
Вы перестаете проверять коэффициенты на n/2, есть ли у вас причина останавливаться на этом ?
Думать об этом:
Каково минимальное кратное 3, которое не является кратным 2 ?
Каково минимальное кратное 5, которое не является кратным 2 или 3 ?
Каков минимальный кратный 7, который не является кратным 2, 3 или 5 ?
Для каждого из этих чисел, каково их произведение простых чисел ?
Ответы должны привести вас к более эффективному верхнему пределу.

Как только вы узнаете, что 2 не является фактором, нужно ли вам проверять факторы 4, 6, 8, 10, 12 ... ?

Совет: Определите функцию IsPrime() который будет проверять, является ли целое число простым или нет. Это позволит отделить проблемы в вашем коде.

Мы не делаем вашу домашнюю работу.

Рейтинг:
1

OriginalGriff

В дополнение к тому, что говорит Ричард, у вас есть очень большой диапазон чисел - 1:1 000 000 000 - это большой диапазон, - и вы делаете, вероятно, 10 тестовых случаев.
И для каждого отдельного числа в этом диапазоне вы повторяете вложенные циклы без какой-либо ссылки на предыдущие решения, используя модифицированный алгоритм сита. Это просто неэффективно, и я сомневаюсь, что даже улучшение его до квадратного корня из верхнего числа улучшит его достаточно.

Начать читать: Каков наилучший алгоритм проверки того, является ли число простым? - Кворум[^] - есть и другие способы сделать это, которые могут привести вас к ограничению по времени. Но вам почти наверняка придется написать код, который будет намного эффективнее, чем у вас есть на данный момент!