Almost Prime – Omówienie zadania

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
Zadanie pochodzi z najpopularniejszej paltformy programistycznej Codeforces.
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
——-

#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% 

 

Liczba komentarzy: 3

Dodaj komentarz