Szczegółowe omówienie zadania Almost Prime:
Link do powyższego omówienia zadania Almost Prime:
https://youtu.be/AcWCajYtYoI?t=1312
——-
Link do treści zadania Almost Prime:
—–
Zadanie Almost Prime to najtrudniejsze zadanie z II etapu VII Olimpiady Informatycznej Gimnazjalistów – poprzednika Olimpiady Informatycznej Juniorów.
Link do wszystkich zadań z Olimpiady Informatycznej Juniorów:
——
Zadanie Almost Prime pokazuje Sito Eratostenesa w wersji rozszerzonej – w tablicy zapisujemy najmniejszy dzielnik każdej liczby:
https://youtu.be/AcWCajYtYoI?t=2305
https://youtu.be/AcWCajYtYoI?t=2305
Zadanie pochodzi z najpopularniejszej paltformy programistycznej Codeforces.
Daje piękny wpis do CV:
https://youtu.be/AcWCajYtYoI?t=5337
Daje piękny wpis do CV:
https://youtu.be/AcWCajYtYoI?t=5337
———-
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
https://youtu.be/QgLyXYmFQeU?t=2019
——-
–
#include <bits/stdc++.h>
using namespace std;
const int MAX_PRIME = 3e3 + 7; //3007
int sieve [MAX_PRIME]; //wypelniona zerami
void Sieve() {
int i,j, max_analized;
sieve[0] = 1;
sieve[1] = 1;
for (i=2; i<MAX_PRIME; ++i) {
if (sieve[i] > 0)
continue;
sieve[i] = i;
for (j=i*i; j<MAX_PRIME; j=j+i) {
if (sieve[j] == 0)
sieve[j] = i;
}
}
}
int main() {
int i;
int range, number, number_divided;
int divisor1, divisor2, current_divisor;
int amount_of_almost_primes;
bool is_number_almost_prime;
Sieve();
cin >> range; //przyklad1 - do 10 (od 1 do 10)
amount_of_almost_primes = 0;
for (number=2; number<=range; ++number) {
is_number_almost_prime = true;
divisor1 = sieve[number]; //2
divisor2 = 0;
number_divided = number; //24
while ( 1 ) {
number_divided = number_divided / sieve[number_divided]; //24:2 -> 12
if ( number_divided <= 1 )
break;
if (sieve[number_divided] == divisor1) //15
continue;
//powyzej kod gdy cay czas w tablicy sieve jest ten sam dzielnik divisor1
//jesli jestesmy tu to pojawil sie nowy dzielnik - divisor2
if (divisor2 == 0) {
divisor2 = sieve[number_divided];
continue;
}
if (sieve[number_divided] == divisor2)
continue;
//jesli jestemy tu to znaczy ze pojawil sie 3 dzielnik - trzecia liczba pierwsza
//jest to nielegalne dla liczb prawie pierwszych
is_number_almost_prime = false;
break;
}
if (is_number_almost_prime == true) //nie bylo wiecej niz 2 dzielniki
if (divisor2 != 0) //pojawil sie 2 dzielnik
++amount_of_almost_primes;
}
cout << amount_of_almost_primes << "\n";
return 0;
}
Kod C++ programu Almost Prime, który jest omówiony w powyższym filmie i który otrzymuje 100%
fajne
Dobre