Szczegółowe omówienie zadania T-primes:

Link do powyższego omówienia zadania T-primes: https://youtu.be/btHSRzo4KMQ?t=1264
Omówienie kodu zadania T-primes: https://youtu.be/btHSRzo4KMQ?t=3732
Kroki algorytmu: https://youtu.be/btHSRzo4KMQ?t=3210
Złożoność algorytmu: https://youtu.be/btHSRzo4KMQ?t=3541

Link do treści zadania T-primes i możliwości umieszczania rozwiązań: https://codeforces.com/problemset/problem/230/B

Zadanie T-primes pokazuje zastosowanie Sita Eratostenesa: https://youtu.be/btHSRzo4KMQ?t=1749
Złożoność Sita Eratostenesa: https://youtu.be/btHSRzo4KMQ?t=2508
Kod Sita Eratostenesa: https://youtu.be/btHSRzo4KMQ?t=3764
Dlaczego zaczynamy wykreślać od i*i w sicie Eratostenesa? https://youtu.be/btHSRzo4KMQ?t=3807

Zadanie z Codeforces! https://youtu.be/gTEmPXiN53U?t=13
Pozwala stworzyć fantastyczne CV! https://youtu.be/gTEmPXiN53U?t=5557

–
Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/
Zajęcia: : https://oki.org.pl/harmonogram-zajec/

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109

–
Kod C++ programu T-primes, który jest omówiony w powyższym filmie i który otrzymuje 100%

–

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
bool zlozona[MAXN];
// zwraca pierwiastek z x jeżeli jest całkowity
// -1 w przeciwnym wypadku
int BinarySearch(long long x)
{
int lewo = 1;
int prawo = 1e6;
while (lewo < prawo) {
int srodek = (lewo + prawo) / 2;
if ((long long)srodek*srodek >= x)
prawo = srodek;
else
lewo = srodek + 1;
}
if ((long long)lewo*lewo != x)
return -1;
return lewo;
}
// sito Eratostenesa
void sito()
{
for (int i = 2; i * i < MAXN; i++) {
if (zlozona[i] == false) {
for (int j = i * i; j < MAXN; j += i)
zlozona[j] = true;
}
}
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
sito();
zlozona[1] = true; // to nie jest prawda, ale przyda się na potrzeby zadania
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
long long x;
cin >> x;
int pierwiastek = BinarySearch(x);
if ((pierwiastek == -1) || (zlozona[pierwiastek]))
cout << "NO\n";
else
cout << "YES\n";
}
return 0;
}

–
Kod Python programu T-primes, który otrzymuje 100%:

MAXN = 1000000 + 7
zlozona = [False] * MAXN
# zwraca pierwiastek z x jeżeli jest całkowity
# -1 w przeciwnym wypadku
def BinarySearch(x):
lewo = 1
prawo = 1000000
while (lewo < prawo): srodek = (lewo + prawo) // 2 if (srodek*srodek >= x):
prawo = srodek
else:
lewo = srodek + 1
if (lewo*lewo != x):
return -1
return lewo
# sito Eratostenesa
def sito():
i = 2
while (i * i < MAXN):
if (zlozona[i] == False):
for j in range(i*i, MAXN, i):
zlozona[j] = True
i += 1
sito()
zlozona[1] = True # to nie jest prawda, ale przyda się na potrzeby zadania
n = int(input())
liczby = map(int, input().split())
for x in liczby:
pierwiastek = BinarySearch(x)
if ((pierwiastek == -1) or (zlozona[pierwiastek])):
print("NO")
else:
print("YES")