Liczby względnie pierwsze

Szukalem sporo po necie, znalazlem rozne informacje, ale moze ktos powiedziec w jaki sposob najszybciej obliczyc funkcje phi (tocjent) dla roznych liczb? Mam takie zadanie:

Your task is to write an arithmetic function that counts the number of positive numbers less than or equal to n that are relatively prime to n. Two integers a and b are said to be relatively prime if the only positive integer that evenly divides both of them is 1. For example, 14 and 15 are relatively prime, being commonly divisible by only 1, but 14 and 21 are not, because they are both divisible also by 7.

i potrzebuje napisac algorytm, ktory dziala mozliwie szybko. Testowalem rozne mozliwosci i najszybciej do tej pory zadzialal mi algorytm oparty na rozkladzie liczby, z ktorej licze tocjent na czynniki i skorzystaniu z tego, ze tocjent tej liczby to iloczyn tocjentow ich czynnikow prostych podniesionych do potegi takiej, ile razy wystepuja w rozkladzie, np. majac liczbe 12 i chcac z niej liczyc tocjent rozkladam ja na czynniki proste: 12=223

teraz tocjent(12)=tocjent(2^2)*tocjent(31)=tocjent(4)tocjent(3)=22=4

Rozklad na liczby pierwsze robie najszybszym algorytmem jaki znalazlem. Wejscie i wyjscie sa rowniez mozlwie zoptymalizowane, jednak algorytm potrzebuje jeszcze bardziej przyspieszyc.

Czy jest jakis sposob na przyspieszenie takiego algorytmu?

Najpierw generujesz sobie tablicę liczb pierwszych, ale zapamiętujesz tylko ich ilość do tego miejsca a nie jakie to są i następnie masz szukanie w czasie O(1).

http://edu.i-lo.tarnow.pl/inf/alg/001_search/0007.php

winerfresh napisał(a):

Najpierw generujesz sobie tablicę liczb pierwszych, ale zapamiętujesz tylko ich ilość do tego miejsca a nie jakie to są i następnie masz szukanie w czasie O(1).

Ale co mi daje ilość pierwszych do danego miejsca? Jeśli wezmę, np. 10 to mnie nie interesuje przecież ile jest liczb pierwszych od 1 do 10 tylko ile jest liczb względnie pierwszych w odniesieniu do 10.

A jak wielkie "n" ?
"Rozklad na liczby pierwsze robie najszybszym algorytmem jaki znalazlem", a co znalazłeś?

Max zakres N to 9998. To czy użyć GNFS czy coś innego?
EDIT: Już sobie dałem radę, dzięki za porady :) Najpierw sitem zrobiłem sobie tablicę liczb pierwszych, a następnie uwzględniłem fakt, że dla liczb pierwszych odpowiedź jest z góry znana, więc dla nich w czasie stałym da się odpowiedzieć, natomiast dla liczb, które nie są pierwsze zrobiłem jak powyżej napisałem (czyli faktoryzacja + obliczanie tocjentów dla czynników).

int ef[9999]={... :-)

Dzięki Zjarek i Xitami ;)