Totient function: Difference between revisions

=={{header|BASIC}}==

<syntaxhighlight lang="gwbasic">10 DEFINT A-Z: DIM B$(2): B$(0)="No": B$(1)="Yes"

20 PRINT " N Totient Prime"

30 FOR N=1 TO 25

40 GOSUB 200

50 P=-(T=N-1)

60 C=C+P

70 PRINT USING "## ####### \ \";N;T;B$(P)

80 NEXT N

90 F$="Number of primes up to ######: ####"

100 PRINT USING F$;25;C

110 FOR N=26 TO 10000

120 GOSUB 200

130 C=C-(T=N-1)

140 IF N=100 OR N=1000 OR N=10000 THEN PRINT USING F$;N;C

150 NEXT N

160 END

200 REM T = TOTIENT(N)

210 T=N: Z=N

220 I=2: GOSUB 270

230 I=3

240 IF I*I<=Z THEN GOSUB 270: I=I+2: GOTO 240

250 IF Z>1 THEN T=T-T\Z

260 RETURN

270 IF Z MOD I<>0 THEN RETURN

280 IF Z MOD I=0 THEN Z = Z\I: GOTO 280

290 T = T-T\I

300 RETURN</syntaxhighlight>

{{out}}

<pre> N Totient Prime

1 1 No

2 1 Yes

3 2 Yes

4 2 No

5 4 Yes

6 2 No

7 6 Yes

8 4 No

9 6 No

10 4 No

11 10 Yes

12 4 No

13 12 Yes

14 6 No

15 8 No

16 8 No

17 16 Yes

18 6 No

19 18 Yes

20 8 No

21 12 No

22 10 No

23 22 Yes

24 8 No

25 20 No

Number of primes up to 25: 9

Number of primes up to 100: 25

Number of primes up to 1000: 168

Number of primes up to 10000: 1229</pre>