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:
am folosit vector caracteristic pe biţi în care am făcut ciurul lui Eratostene pentru a memora numerele prime.
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.
