Radical of an integer: Difference between revisions
Added XPL0 example.
(→{{header|Free Pascal}}: added modified fast consecutive factors of integer. Yes, it's lengthy.) |
(Added XPL0 example.) |
||
Line 1,252:
78,735
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">include xpllib; \for Print and IsPrime
proc Radical(N); \Return radical of N
int N, D, D0, P;
[D:= 2; D0:= 0; P:= 1;
while N >= D*D do
[while rem(N/D) = 0 do
[if D # D0 then
[P:= P*D;
D0:= D;
];
N:= N/D;
];
D:= D+1;
];
if D # D0 then P:= P*N;
return P;
];
func DistinctFactors(N); \Return count of distinct factors of N
int N, D, D0, C;
[D:= 2; D0:= 0; C:= 0;
while N >= D*D do
[while rem(N/D) = 0 do
[if D # D0 then
[C:= C+1;
D0:= D;
];
N:= N/D;
];
D:= D+1;
];
if D # D0 and N # 1 then C:= C+1;
return C;
];
int N, C, A(10), PC, PPC, P2, P;
[Print("The radicals for the first 50 positive integers are:\n");
for N:= 1 to 50 do
[Print("%4d", Radical(N));
if rem(N/10) = 0 then CrLf(0);
];
Print("\n");
Print("Radical for %6,d: %6,d\n", 99_999, Radical( 99_999));
Print("Radical for %6,d: %6,d\n", 499_999, Radical(499_999));
Print("Radical for %6,d: %6,d\n", 999_999, Radical(999_999));
for N:= 0 to 9 do A(N):= 0;
for N:= 1 to 1_000_000 do
[C:= DistinctFactors(N);
A(C):= A(C)+1;
];
Print("\nBreakdown of numbers of distinct prime factors
for positive integers from 1 to 1,000,000:\n");
C:= 0;
for N:= 0 to 9 do
[if A(N) > 0 then
Print(" %d: %6,d\n", N, A(N));
C:= C + A(N);
];
Print(" ---------\n %,d\n", C);
\Bonus (algorithm from Wren):
PC:= 0;
for N:= 1 to 1_000_000 do
if IsPrime(N) then PC:= PC+1;
Print("\nNumber of primes: %5,d\n", PC);
PPC:= 0;
for P:= 1 to sqrt(1_000_000) do
[if IsPrime(P) then
[P2:= P;
loop [P2:= P2 * P;
if P2 > 1_000_000 then quit;
PPC:= PPC+1;
];
];
];
Print("Number of powers: %5,d\n", PPC);
if IsPrime(N) then PC:= PC+1;
Print("Total : %5,d\n", PC+PPC);
]</syntaxhighlight>
{{out}}
<pre>
The radicals for the first 50 positive integers are:
1 2 3 2 5 6 7 2 3 10
11 6 13 14 15 2 17 6 19 10
21 22 23 6 5 26 3 14 29 30
31 2 33 34 35 6 37 38 39 10
41 42 43 22 15 46 47 6 7 10
Radical for 99,999: 33,333
Radical for 499,999: 3,937
Radical for 999,999: 111,111
Breakdown of numbers of distinct prime factors
for positive integers from 1 to 1,000,000:
0: 1
1: 78,734
2: 288,726
3: 379,720
4: 208,034
5: 42,492
6: 2,285
7: 8
---------
1,000,000
Number of primes: 78,498
Number of powers: 236
Total : 78,734
</pre>
| |||