Urgent!
Cerința
Dorel are o nouă pasiune, să coloreze divizorii unui număr natural. Primind cadou de ziua lui un număr natural n, s-a gândit să coloreze toate numerele naturale de la 1 la n cu câte o culoare, astfel încât toţi divizorii proprii ai unui număr să aibă aceeaşi culoare cu numărul. Vă roagă pe voi să aflaţi care este numărul maxim de culori care pot fi folosite.
Date de intrare
Fișierul de intrare primcolor.in conține pe prima linie numărul n.
Date de ieșire
Fișierul de ieșire primcolor.out va conține pe prima linie numărul maxim de culori ce pot fi folosite.
Restricții și precizări
1 ≤ n ≤ 50.000.000
Exemplu
primcolor.in
5
primcolor.out
4
Răspunsuri la întrebare
Răspuns:
#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream f("primcolor.in");
ofstream g("primcolor.out");
bitset <50000000>v;
int n, c, num, i,j,mij;
bool prim(int x)
{
if (x%2==0) return false;
for (int j=3; j*j<=x; ++j)
if (x%j==0) return false;
return true;
}
int main()
{
for (i=2; i<50000000; ++i) v[i]=1;
v[0]=0; v[1]=0;
for(i=2;i<=25000000;++i)
if(v[i]==1)
for(j=i+i;j<=50000000;j+=i)
v[j]=0;
f >> n;
if (n<4) c=n;
else{
c=2; mij=n/2+1;
if (mij%2==0) ++mij;
for (num=mij; num<=n; num+=2)
c+=v[num];
}
g << c;
}
Explicație:
Poate îţi vor fi de ajutor Indicaţiile:
Numărul 1 se colorează cu c1 iar numărul 2 cu c2. Toate numerele pare vor fi colorate cu c2 deoarece au divizor propriu pe 2. Toate numerele mai mici sau egale cu n/2 au un multiplu par mai mic sau egal cu n care are deja culoarea c2, deci vor avea obligatoriu culoarea c2. Toate numerele compuse cuprinse între n/2+1 şi n au un divizor mai mic sau egal cu n/2, deci şi acestea au obligatoriu culoarea c2. Numerele prime cuprinse între n/2 şi n+1 pot fi colorate cu culori distincte, deoarece nu au nici divizori proprii, nici multiplii mai mici sau egali cu n. Astfel numărul de culori va fi 2 plus numărul numerelor prime cuprinse între n/2 şi n+1.