T-primes – Codeforces – Omówienie zadania – Sito Eratostenesa

T-primes – Codeforces – Omówienie zadania – Sito Eratostenesa

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 C++ programu T-primes, który jest omówiony w powyższym filmie i który otrzymuje 100%

 


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")

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz