how to calculate euler phi function of integer from 1 to n effectively?

[rabbit_dance]

how to calculate euler phi function of integer from 1 to n effectively?

[rabbit_dance]

i have written a program which can't be compiled to calculate this problem.

[rabbit_dance]

how to revise the following source code?

Code: [Select]

PROGRAM EULER_PHI;
TYPE LINKED_PTR=^LINK_NODE;
        LINK_NODE=RECORD
        VALUE:INTEGER;
        NEXT:LINKED_PTR;
END;
VAR N,M,I:INTEGER;VAR NODE,G:LINKED_PTR;
PROCEDURE PRINTING(PTR:LINKED_PTR);
VAR R:INTEGER;VAR P:LINKED_PTR;
BEGIN
R:=1;P:=PTR;
REPEAT
    P:=P^.NEXT;
    WRITE('  ',R,' ',P^.VALUE);
    R:=R+1;
UNTIL(PTR^.NEXT=NIL);
END;
PROCEDURE SUCCESSOR(VAR PTR:LINKED_PTR);
VAR P:LINKED_PTR;
BEGIN
    IF PTR^.NEXT=NIL THEN BEGIN
        (*CREATE A NEW NODE AND LINK IT TO PREVIOUS ONE*)
        PTR^.NEXT:=ALLOCMEM(SIZEOF(LINK_NODE));
        P:=PTR^.NEXT;
        PTR:=P; (*CHANGE CURRENT POINTER*)
END
ELSE BEGIN (*FIND AND CHANGE THE NEXT*)
        P:=PTR^.NEXT;PTR:=P;
END;
END;
PROCEDURE ASSIGNMENT(VAR PTR:LINKED_PTR);
BEGIN
        SUCCESSOR(PTR);PTR^.VALUE=0;
END;
PROCEDURE TRAVERSE_ELEMENTS(VAR O:LINKED_PTR; K:INTEGER);
VAR T:INTEGER;
BEGIN
    FOR T:=1 TO K DO
    BEGIN
        SUCCESSOR(O);
    END;
END;
BEGIN
READLN(N);
NODE:=ALLOCMEM(SIZEOF(LINK_NODE));
NODE^.VALUE=1;G:=NODE;
FOR M:=2 TO N DO
BEGIN
        ASSIGNMENT(NODE);
END;
M:=2;NODE:=G;
WHILE(M<=N) DO
BEGIN
        TRAVERSE_ELEMENTS(NODE,M);
        IF NODE^.VALUE=0 THEN BEGIN
            I:=M;
            WHILE(I<=N) DO
            BEGIN
                TRAVERSE_ELEMENTS(G,I);
                IF G^.VALUE=0 THEN G^.VALUE=I;
                G^.VALUE:=G^.VALUE/M*(M-1);
                I:=I+M;
            END;
            M:=M+1;
        END;
END;
PRINTING(NODE);
READLN();
END.



[Eugene Loza]

Wow... why so complex??? https://en.wikipedia.org/wiki/Euler's_totient_function
It's just about

Code: [Select]

Phi:=1;
for i:=2 to N do begin
   RelativelyPrime:=true;
   for j:=2 to i do if i mod j =0 then
     if N mod j = 0 then RelativelyPrime:=false;
  if RelativelyPrime then inc(Phi);
end;I haven't tested the code, but definitely there's no need for pointers, etc.
There's another way to calculate Phi: https://en.wikipedia.org/wiki/Euler's_totient_function#Computing_Euler.27s_totient_function
But I haven't tested its efficiency, it might be even less efficient (for N<1000000) due to multiple calculation of prime numbers. And definitely the complex code would need a lot of debugging.

[rabbit_dance]

why so complex? because i want to design a most efficiency program.
which program is more efficient?

[rabbit_dance]

i have revised my code, but the program could not be normally executed after compilation!

[rabbit_dance]

Code: [Select]

PROGRAM EULER_PHI;
TYPE LINKED_PTR=^LINK_NODE;
        LINK_NODE=RECORD
        VALUE:INTEGER;
        NEXT:LINKED_PTR;
END;
VAR N,M,I,R:INTEGER;VAR NODE,G:LINKED_PTR;
PROCEDURE PRINTING(PTR:LINKED_PTR);
VAR P:LINKED_PTR;
BEGIN
P:=PTR;
P:=P^.NEXT;
WRITE('  ',R,' ',P^.VALUE);
IF P^.NEXT=NIL THEN EXIT();
PRINTING(P);
R:=R+1;
FREEMEM(P,SIZEOF(LINKED_PTR));
END;
PROCEDURE SUCCESSOR(VAR PTR:LINKED_PTR);
VAR P:LINKED_PTR;
BEGIN
    IF PTR^.NEXT=NIL THEN BEGIN
        (*CREATE A NEW NODE AND LINK IT TO PREVIOUS ONE*)
        PTR^.NEXT:=ALLOCMEM(SIZEOF(LINK_NODE));
        P:=PTR^.NEXT;PTR:=P;
END;
END;
PROCEDURE ASSIGNMENT(PTR:LINKED_PTR);
BEGIN
        SUCCESSOR(PTR);
END;
PROCEDURE TRAVERSE_ELEMENTS(O:LINKED_PTR; VAR Q:LINKED_PTR;K:INTEGER);
VAR T:INTEGER;
BEGIN
    FOR T:=1 TO K DO
    BEGIN
        SUCCESSOR(O);
    END;
    Q:=O;
END;
BEGIN
R:=1;
READLN(N);
NODE:=ALLOCMEM(SIZEOF(LINK_NODE));
NODE^.VALUE:=1;
FOR M:=2 TO N DO
BEGIN
        ASSIGNMENT(NODE);
END;
M:=2;NODE:=G;
WHILE(M<=N) DO
BEGIN
        TRAVERSE_ELEMENTS(NODE,G,M);
        IF G^.VALUE=0 THEN BEGIN
            I:=M;
            WHILE(I<=N) DO
            BEGIN
                TRAVERSE_ELEMENTS(NODE,G,I);
                IF G^.VALUE=0 THEN G^.VALUE:=I;
                G^.VALUE:=(G^.VALUE DIV M)*(M-1);
                I:=I+M;
            END;
            M:=M+1;
        END;
END;
PRINTING(NODE);
READLN();
END.



[rabbit_dance]

Code: [Select]

PROGRAM EULER_PHI;
TYPE LINKED_PTR=^LINK_NODE;
        LINK_NODE=RECORD
        VALUE:INTEGER;
        NEXT:LINKED_PTR;
END;
VAR N,M,I,R:INTEGER;VAR NODE,G:LINKED_PTR;
PROCEDURE PRINTING(PTR:LINKED_PTR);
VAR P:LINKED_PTR;
BEGIN
P:=PTR;
P:=P^.NEXT;
WRITE('  ',R,' ',P^.VALUE);
IF P^.NEXT=NIL THEN EXIT();
PRINTING(P);
R:=R+1;
FREEMEM(P,SIZEOF(LINKED_PTR));
END;
PROCEDURE SUCCESSOR(VAR PTR:LINKED_PTR);
VAR P:LINKED_PTR;
BEGIN
    IF PTR^.NEXT=NIL THEN BEGIN
        (*CREATE A NEW NODE AND LINK IT TO PREVIOUS ONE*)
        PTR^.NEXT:=ALLOCMEM(SIZEOF(LINK_NODE));
        P:=PTR^.NEXT;PTR:=P;
END;
END;
PROCEDURE ASSIGNMENT(PTR:LINKED_PTR);
BEGIN
        SUCCESSOR(PTR);
END;
PROCEDURE TRAVERSE_ELEMENTS(O:LINKED_PTR; VAR Q:LINKED_PTR;K:INTEGER);
VAR T:INTEGER;
BEGIN
    FOR T:=1 TO K DO
    BEGIN
        SUCCESSOR(O);
    END;
    Q:=O;
END;
BEGIN
R:=1;
READLN(N);
NODE:=ALLOCMEM(SIZEOF(LINK_NODE));
NODE^.VALUE:=1;
FOR M:=2 TO N DO
BEGIN
        ASSIGNMENT(NODE);
END;
M:=2;NODE:=G;
WHILE(M<=N) DO
BEGIN
        TRAVERSE_ELEMENTS(NODE,G,M);
        IF G^.VALUE=0 THEN BEGIN
            I:=M;
            WHILE(I<=N) DO
            BEGIN
                TRAVERSE_ELEMENTS(NODE,G,I);
                IF G^.VALUE=0 THEN G^.VALUE:=I;
                G^.VALUE:=(G^.VALUE DIV M)*(M-1);
                I:=I+M;
            END;
            M:=M+1;
        END;
END;
PRINTING(NODE);
READLN();
END.



[bytebites]

First you initialize variable NODE and then assign uninitialized variable G to it.

[rabbit_dance]

thanks. but my program still could not output properly.

[rabbit_dance]

Code: [Select]

PROGRAM EULER_PHI;
TYPE LINKED_PTR=^LINK_NODE;
        LINK_NODE=RECORD
        VALUE:INTEGER;
        NEXT:LINKED_PTR;
END;
VAR N,M,I,R:INTEGER;VAR NODE,G:LINKED_PTR;
PROCEDURE PRINTING(PTR:LINKED_PTR);
VAR P:LINKED_PTR;
BEGIN
P:=PTR;
P:=P^.NEXT;
R:=R+1;
WRITE('  ',R,' ',P^.VALUE);
IF P^.NEXT=NIL THEN EXIT();
PRINTING(P);
FREEMEM(P,SIZEOF(LINKED_PTR));
END;
PROCEDURE SUCCESSOR(VAR PTR:LINKED_PTR);
VAR P:LINKED_PTR;
BEGIN
    IF PTR^.NEXT=NIL THEN BEGIN
        (*CREATE A NEW NODE AND LINK IT TO PREVIOUS ONE*)
        PTR^.NEXT:=ALLOCMEM(SIZEOF(LINK_NODE));
END;
        P:=PTR^.NEXT;PTR:=P;
END;
PROCEDURE ASSIGNMENT(PTR:LINKED_PTR);
BEGIN
        SUCCESSOR(PTR);
END;
PROCEDURE TRAVERSE_ELEMENTS(O:LINKED_PTR; VAR Q:LINKED_PTR;K:INTEGER);
VAR T:INTEGER;
BEGIN
    FOR T:=1 TO K DO
    BEGIN
        SUCCESSOR(O);
    END;
    Q:=O;
END;
BEGIN
R:=1;
READLN(N);
NODE:=ALLOCMEM(SIZEOF(LINK_NODE));
NODE^.VALUE:=1;
FOR M:=2 TO N DO
BEGIN
        ASSIGNMENT(NODE);
END;
M:=2;NODE:=G;
WHILE(M<=N) DO
BEGIN
        TRAVERSE_ELEMENTS(NODE,G,M);
        IF G^.VALUE=0 THEN BEGIN
            I:=M;
            WHILE(I<=N) DO
            BEGIN
                TRAVERSE_ELEMENTS(NODE,G,I);
                IF G^.VALUE=0 THEN G^.VALUE:=I;
                G^.VALUE:=(G^.VALUE DIV M)*(M-1);
                I:=I+M;
            END;
            M:=M+1;
        END;
END;
PRINTING(NODE);
READLN();
END.



[Bart]

Still problems with the CapsLock key? 

Bart

[rabbit_dance]

what's your problem?

[molly]

what's your problem?

It's not only Bart's problem.

Style guide from gnu pascal and style guide from embarcadero. Do we have one on our own wiki's ?

Not only is your source-code hard to read this way, it's also pretty much outdated as writing with all capitals stems from the early DOS days. Also some people consider it as shouting.

So Bart simply asked if your caps-lock key has broken down 

[Bart]

what's your problem?

My problem (as explained to you in another thread) is, that it is hard to read text (code) that is in all capitals.
Reading to me (and probably most western-european etc.) comes more natural if written "natural" (for lack of a better word): use capitals where you would use it when you would write a normal sentence.
For programming languages like Pascal (that do not make a distinction between upper- and lowercase) uppercasing can be used to emphasize or to make better reading of certain words e.g.

Code: [Select]

procedure CalculateEvenCatalanNumbers;  //this way of using capitals is called CamelCase
vs
procedure calculateevencatalannumbers; 
vs
procedure CALCULATEEVENCATALANNUMBERS;

For me the first one makes it obvious in one glance what the procedure is meant to do.

Proper indentation (use the same style of indentation everywhere) and separation of procedures/functions also helps.

Code: [Select]

PROCEDURE PRINTING(PTR:LINKED_PTR);
VAR P:LINKED_PTR;
BEGIN
P:=PTR;
P:=P^.NEXT;
R:=R+1;
WRITE('  ',R,' ',P^.VALUE);
IF P^.NEXT=NIL THEN EXIT();
PRINTING(P);
FREEMEM(P,SIZEOF(LINKED_PTR));
END;
PROCEDURE SUCCESSOR(VAR PTR:LINKED_PTR);
VAR P:LINKED_PTR;
BEGIN
    IF PTR^.NEXT=NIL THEN BEGIN
        (*CREATE A NEW NODE AND LINK IT TO PREVIOUS ONE*)
        PTR^.NEXT:=ALLOCMEM(SIZEOF(LINK_NODE));
        P:=PTR^.NEXT;PTR:=P;
END;
END;

Versus

Code: [Select]

procedure Printing(Ptr: Linked_Ptr);
var
  P:Linked_Ptr;
begin
  P:=Ptr;
  P:=P^.Next;
  R:=R+1;
  Write('  ',R,' ',P^.Value);
  IF P^.Next=nil then Exit();
  Printing(P);
  FreeMem(P,SizeOf(Linked_Ptr));
end;

procedure Successor(var Ptr:Linked_Ptr);
var
  P:Linked_Ptr;
begin
  if Ptr^.Next=nil then
  begin
    (*Create a new node and link it to previous one*)
    Ptr^.Next:=AllocMeM(SiseOf(Link_Node));
  end;
  P:=Ptr^.Next;
  Ptr:=P;
end;

It's so much less strain on the eyes.

Bart