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

[ruivit]

В общим написал код, так то он работает, но на проверку ещё не отправлял.

#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 i = 10, Q, N, X;
     char KU[200000]; // 20 000 000 тут должно быть это число
     int s = 0;
     int pt;

     cin >> N >> Q;

     while(i < N){ // Диапозон чисел 
     	i++;
     	if(sultan(i))
		 {
		 ///	cout << i << " prime" << endl; // простое (проверка на первой стадии )			 	
		 	KU[i] = 'X';
		 	
		 } else{
		 // 	cout << i << " no" << endl; // простое (проверка на первой стадии )	
		 	KU[i] = 'Y';
		 }
	}
	  	while(s < 200 ){ // число запросов должно быть 200 000
	  		
		s++;

		if((KU[s] == 'X') || (KU[s]== 'Y')) { // начала отсчёта строк
		
		if(pt < Q){  // начинаем считать с роки 
		pt++;
		
		 if(KU[s] == 'X') {
		 	
	  	 cout << pt << " prime" << endl;
		   		     				     		
		} else if(KU[s] == 'Y') {
			
			
	 		cout << pt << " no"  << endl;	     				     		
         
		}	   
		   		     				     		   
														       
} 
	  	
}
	
}
    return 0;
}

[ruivit]

Вот написал код вроде вот работает но на проверку ещё не отпровлял :

#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 i = 10, Q, N, X;
     char KU[200000]; // 20 000 000 тут должно быть это число
     int s = 0;
     int pt;

     cin >> N >> Q;

     while(i < N){ // Диапозон чисел 
     	i++;
     	if(sultan(i))
		 {
		 ///	cout << i << " prime" << endl; // простое (проверка на первой стадии )			 	
		 	KU[i] = 'X';
		 	
		 } else{
		 // 	cout << i << " no" << endl; // простое (проверка на первой стадии )	
		 	KU[i] = 'Y';
		 }
	}
	  	while(s < 200 ){ // число запросов должно быть 200 000
	  		
		s++;

		if((KU[s] == 'X') || (KU[s]== 'Y')) { // начала отсчёта строк
		
		if(pt < Q){  // начинаем считать с роки 
		pt++;
		
		 if(KU[s] == 'X') {
		 	
	  	 cout << pt << " prime" << endl;
		   		     				     		
		} else if(KU[s] == 'Y') {
			
			
	 		cout << pt << " no"  << endl;	     				     		
         
		}	   
		   		     				     		   
														       
} 
	  	
}
	
}
    return 0;
}

[macomics]

Сообщение от ruivit

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

Я вам уже дал подсказку насчет четных чисел. Почему у вас до сих пор поиск проходит с перебором всех подряд?

bool sultan(int n) 
{
    if (n <= 1)
        return false;
    if (n & 1 == 0)
        return n == 2;
    for (int i = 3; i * i <= n; i+= 2) 
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

У вас должно быть два подряд цикла, не вложенных. В первом вам надо найти все простые числа в диапазоне 2 .. N, а во втором вы считываете X и проверяете их на присутствие в массиве простых чисел.

Еще одна подсказка. Проверка на сомножители/делимость надо проводить только если делитель простое число. Согласитесь, что если число не делится на 3, тогда проверять его делимость на 9 - уже бесполезно, а на 27 - тем более.

Сообщение от ruivit

int i = 10, Q, N, X;

Почему вычисления начинаются с 10, а не с 2?

Сообщение от ruivit

while(s < 200 ){

Почему 200, а не Q

Сообщение от ruivit

if((KU[s] == 'X') || (KU[s]== 'Y')) { // начала отсчёта строк

Это условие бессмысленное т.к. в предыдущем цикле вы уже должны переопределить все значения в диапазоне 0 .. N и они будут все определены либо как X либо как Y.

Сообщение от ruivit

if(pt < Q){  // начинаем считать с роки 
		pt++;
		
		 if(KU[s] == 'X') {
		 	
	  	 cout << pt << " prime" << endl;
		   		     				     		
		} else if(KU[s] == 'Y') {
			
			
	 		cout << pt << " no"  << endl;

Вам надо просто считывать Q раз значения X из консоли через cin. А вы что тут делаете?

[ruivit]

Цитата:
Сообщение от ruivit Посмотреть сообщение
Код:
if(pt < Q){  // начинаем считать с роки 
		pt++;
		
		 if(KU[s] == 'X') {
		 	
	  	 cout << pt << " prime" << endl;
		   		     				     		
		} else if(KU[s] == 'Y') {
			
			
	 		cout << pt << " no"  << endl;
Вам надо просто считывать Q раз значения X из консоли через cin. А вы что тут делаете?

Я просто думал при вводе значений N и Q считывание Х происходит в диапазоне N и выводится X в виде not/print на против номера строки Q. То есть мне значит мне любые числа X надо вводить с консоли Q раз?

[macomics]

А вы еще раз вот тут внимательно посмотрите на колонку input.txt и output.txt и сраните числа в этих строках. У вас там перечислены не порядковые номера, а значения X. Поэтому после 2 идет 4 потом 7 и 5. Не очень это похоже на порядковые номера строк. Зато это совпадает с числами на 1 строку выше в колонке output.txt

[ruivit]

Короче победил я это задание, тут надо было оказывается делать всё горазда проще.

#include <iostream>
using namespace std;
int tus(int ns) {
    if (ns == 1) return false;
    if (ns == 2) return true;
    if (ns % 2 == 0) return false;
    for (int i = 2; i * i <= ns; i++)
        if (ns % i == 0) return false;
    return true;
}

int main() {
    int qe = 0, ne = 0, xe = 0;
    cin >> ne >> qe;
    for (int i = 0; i < qe; i++) {
        cin >> xe;
        if (tus(xe)) cout << xe << " prime" << endl;
        else cout << xe << " not" << endl;
    }
    return 0;
}

[macomics]

Если по времени это прошло, тогда отлично. Но это решение не самое быстрое. Обычно на таких задачках ищут хотя и не самое быстрое, но и не самое медленное решение. Ваш вариант значит не сталкивался с каверзными тестами из тех, что я описал

20000000 200000
19999999
...
19999999

Это самый сложный случай для вашей программы. Сколько же по времени она будет решать этот пример?