SGU 355 : Numbers Painting

Link : sgu355

Category : Simple number theory

Solution :  For every M in 2 to N, let prime factorization of M be M=product(p_i^e_i). Then M will be colored by color number sum(e_i). Eg, 12=2²x3¹, then color 12 by color number (2+1)=3. Additionally, number 1 will require a totally different color, since it divides all other numbers.

Code:

	var n,n0,n1,i,maxfacts,facts:longint;
	colors:array[1..10000] of longint;
	begin
	readln(n0);
	if n0=1 then
	begin
	writeln(1);
	writeln(1);
	exit;
	end;
	maxfacts:=1;
	for n1:=2 to n0 do
	begin
	n:=n1;
	facts:=0;
	i:=2;
	while i*i<=n do
	begin
	if n mod i=0 then
	begin
	while n mod i=0 do
	begin
	n:=trunc(n/i);
	inc(facts);
	end;
	end;
	inc(i);
	end;
	if n>1 then inc(facts);
	if facts>maxfacts then maxfacts:=facts;
	colors[n1]:=1+facts;
	end;
	writeln(maxfacts+1);
	write(1,' ');
	for i:=2 to n0 do
	write(colors[i],' ');
	end.

view raw sgu355.pas hosted with ❤ by GitHub