Не получается найти простые сложные числа.

[ruivit]

В общим есть задача решая которую я вошёл в тупик. "Найдите все простые числа, меньшие 𝑁. В первой строке входного файла содержатся два целых числа: 𝑁 — диапазон, в котором
нужно найти все простые числа и 𝑄 — количество запросов в файле (10 6 𝑁 6 20 000 000,
1 6 𝑄 6 200 000). В каждой из следующих 𝑄 строк содержится по одному целому числу 𝑋, для которого
нужно вывести, простое оно или нет (0 6 𝑋 < &#119873. Должно получится как я понимаю что то вот такое.
Screenshot_3.png

Вот написал программку

#include <iostream>
#include <math.h>
using namespace std;
bool sultan(int n) 
{
    if (n == 1)
        return false; 
    for (int i = 2; i <= sqrt(n); i++) 
    {
        if (n % i == 0)
            return false;
    }
    return true;
}
int main()
{
     int Q, N, X;
     cin >> N >> Q;

     for(int i =0; i < N; i++){
     	X++;
     	if((sultan(i)) && (Q > i) && (0 < i))
		 {
		 	cout << i << "prime" << endl; 	
		 } 
		 else if((sultan(i) == false) && (Q > i) || (0 == i)){
		 	cout << i << "not" << endl;	
		 }	
	 }
    
    return 0;
}

Она выдаёт следующий результат Screenshot_1.png. Но почему то мою программу банят... Ну мол решение не верное. Я вот понять не могу в чём не верное ведь результат то дает же. Согласно примеру

[macomics]

А в примере еще пробелы между числом и определением not/prime

if((sultan(i)) && (Q > i) && (0 < i))
		 {
		 	cout << i << "prime" << endl; 	
		 } 
		 else if((sultan(i) == false) && (Q > i) || (0 == i)){
		 	cout << i << "not" << endl;	
		 }

А вы уверены, что стоит дважды вызывать функцию, которая занимает большую часть времени решения?

ADD: Чему изначально равно X?

Значения i для линейного цикла можно предсказать, поэтому не нужно дополнительных бесполезных проверок в цикле.

Т.е. можно отдельно обработать вне цикла ситуацию i == 0 и не проверять это в цикле от i = 1 до (i < N).

Какой смысл в проверке Q > i, когда можно сразу вычислить E = min(N, Q);

[BDA]

Вам нужно не счетчик цикла i проверять на простоту, а число X из файла. Поэтому и цикл нужно крутить не до N, а до Q. А каким точно образом нужно использовать N, сложно понять, так как в вашем описании задачи диапазоны плохо прописаны.

[digitalis]

Нравится мне постановка задачи: "найти простые сложные числа" . Это как "найти православных мусульман"?
А кстати - что это за "сложные числа" - это со сложной судьбой что ли? В моё студенческое время были простые и составные (но не одновременно!) . Наука, видимо, не стоит на месте...

[ruivit]

Поэтому и цикл нужно крутить не до N

N это диапазон, я как понял диапазон тут от числа 0 до N. Q это число запросов в рамках диапазона от 0 до N По этому я цикл кручу от 0 до N. Но количество простых и сложных чисел не больше Q. Понимаю что глупость, но условие задачи такое. Но а то что нужно не I проверять на простоту, а X. Спасибо за то что указали на ошибку. Я не сразу сообразил причём X. получалось что он не в чём не участвовал раньше. )))

[macomics]

У вас вполне ясное задание. Вы должны в диапазоне 2 .. N найти все простые числа. В условии N ограничен от 10 до 20000000, но конкретно вам это ограничение задается в первом числе файла. Q - количество последующих подстрок, в которых записаны X.

По сути задачи вам надо прости по диапазону от 2 до N (заданному) и вычислить все простые числа в этом диапазоне. После этого пройтись по файлу и считывая X (всего их Q штук) определить является ли значение простым.

Т.е. 2 .. N - диапазон поиска простых чисел и значения X, заданные в файле, лежат в этом диапазоне.
Но само значение N задается в диапазоне от 10 до 20000000.
1 .. Q - количество строк в файле без первой т.к. в ней заданы числа N и Q. Но само значение Q задается в диапазоне 1 .. 200000.

По алгоритму. На первом этапе вы считываете N и Q. Запускаете цикл поиска простых чисел в диапазоне от 2 до N (он будет длиться по времени дольше всего) и сохраняете все простые числа в массив. После цикла поиска простых чисел вы считываете еще Q строк из файла и проверяете присутствие значения X в массиве простых чисел. Если X присутствует в массиве простых чисел, тогда выводите в выходной файл (<< X << ' prime'), иначе выводите (<< X << ' not').

Вместо массива простых чисел возможно использовать битовую карту. Это сэкономит память и ускорит второй этап проверки значений считываемых из файла.

[ruivit]

У вас вполне ясное задание. Вы должны в диапазоне 2 .. N найти все простые числа. В условии N ограничен от 10 до 20000000, но конкретно вам это ограничение задается в первом числе файла. Q - количество последующих подстрок, в которых записаны X.

По сути задачи вам надо прости по диапазону от 2 до N (заданному) и вычислить все простые числа в этом диапазоне. После этого пройтись по файлу и считывая X (всего их Q штук) определить является ли значение простым.

Т.е. 2 .. N - диапазон поиска простых чисел и значения X, заданные в файле, лежат в этом диапазоне.
Но само значение N задается в диапазоне от 10 до 20000000.
1 .. Q - количество строк в файле без первой т.к. в ней заданы числа N и Q. Но само значение Q задается в диапазоне 1 .. 200000.

По алгоритму. На первом этапе вы считываете N и Q. Запускаете цикл поиска простых чисел в диапазоне от 2 до N (он будет длиться по времени дольше всего) и сохраняете все простые числа в массив. После цикла поиска простых чисел вы считываете еще Q строк из файла и проверяете присутствие значения X в массиве простых чисел. Если X присутствует в массиве простых чисел, тогда выводите в выходной файл (<< X << ' prime'), иначе выводите (<< X << ' not').

То есть как я понял N - это диапазоне числе в котором мы ищем простые числа x, ну Q это строки. то есть в каждой Q строке должно быть какое то количество X простых чисел.

[macomics]

Нет. Вам задается Q чисел
INPUT:

N Q
X
X
X
X
.
.
X

Каждое X надо проверить на простоту, но т.к. это повторяющаяся задача, тогда чтобы не выполнять кучу одинаковых манипуляций с числами, стоит создать массив из простых чисел. Длина массива не известна, но известен диапазон поиска простых чисел - это 2 .. N. Сколько вы в этом диапазоне найдете чисел не известно. Но это существенно сократит время работы программы.

Если делать "влоб", тогда вам придется проверять 200`000 раз одни и те же числа на простоту проходя по циклу 1 .. Q

ADD: Представьте себе такой входной файл

20000000 200000
19999999
.
.
19999999

т.е. у вас в строках задается одно и тоже число 200`000 раз, а это число еще и максимально возможное. Значит это будет самый длинный из возможных циклов по Q, а еще и самый долгий поиск для ответа на вопрос о простоте этого же числа (если делать "влоб"). Я не использовал число 20`000`000 т.к. четные числа легко отсеиваются - они все составные, кроме 2 т.к. делятся на 2.

[ruivit]

Понял сейчас попробую решить так задачу.

[macomics]

Можно кстати еще немного схитрить. Искать простые числа не в диапазоне 2 .. N, а в диапазоне 2 .. max(X).
Т.е. вводите первое X и ищите все простые числа в диапазоне 2 .. X. Считываете следующий X и если он меньше или равен предыдущему, тогда у вас уже есть массив, для ответа на вопрос о его простоте, иначе вам надо продолжить поиск простых чисел в диапазоне Xпредыдущее .. Xсчитанное. Но это и значит, что поиск простых чисел будет производиться только в диапазоне от 2 до max(X).