funkcja eulera

[xxxxxx]

czy jest w internecie jakis program ktory oblicza wartosc funkcji eulera?

[Olo]

mogę Ci go napisać

[Hanney]

No ja też bym nie pogardził takim programem:)
no i byłbym wdzieczny:)
albo przynajmniej opisem algorytmu

[Barts20]

Poniwaz nikt tego nie napisał sam napisałem ten program nwd konieczne tutaj wyliczam z algorytmu ekildesa , jego realizacje znalazłem w necie. Program ten dodatkowo zapisuje liczby wzglednie pierwsze z dana i te liczby tworzą grupe z działeniem mnozenie modulo n, stad male ogranicznie w programie który sparawdza liczby z zakresu 1-1000(nie sprawdza poprawnoci wpisanych danych) , program pisałem od reki wiec pewne ulepszenia mozna wrowadzic jak równiez zwiekszyc zakres liczb(lub co by bylo najlepsze zastoswac dynamiczna alkokacje tablicy), ale mam nadzieje ze komus w czyms pomoze
piszcie jak jakies bledy w kodzie czy w dzialaniu

Aha program jest w C++ jesli komus sie nie chce kompilowac moze byc to kwestia kilku poprawek tak by dany kompilator zaakceptował np czy int main (chyba potrzebne w dev c++) ja robilem to w Visualu

Kod: Zaznacz cały

#include <iostream>
using namespace std;


unsigned long NWD(unsigned long a, unsigned long b);
unsigned long Euler(unsigned long n, unsigned long tab[]);


void main()
{
unsigned long n;
unsigned long *tab;
unsigned long p;
char h;

cout<<"FUNKCJA EULERA"<<endl;

cout<<"podaj n"<<endl;
cin>>n;

tab=new unsigned long[n];


p=Euler(n,tab);
cout<<"wynik funkcji to :"<<p<<endl;

cout<<"czy wyswietlic liczby wzhlednie pierwsze z dana :"<<endl;
cout<<"Odpowirdz 't; lub 'T' aby zakceptowac"<<endl;
cin>>h;

if(h=='T' || h=='t')
{
cout<<"Dane liczby tworza grupe z dzialaniem mnozenie modulo n  :";

for (int i=0;i<p; i++)
{
	cout<<tab[i]<<"\t";

}
cout<<endl;
}
}

unsigned long Euler(unsigned long n, unsigned long tab[])
{
	int pom=0;
	

	for(int i=1; i<n;i++)
	{if(NWD(i,n)==1)
	   {
		   tab[pom]=i;
		   pom++;
	    
	   }
	}
return pom;
}


unsigned long NWD(unsigned long a, unsigned long b)
{
  while(a != b) if(a > b) a -= b; else b -= a;
  return(a);
}

[mol_ksiazkowy]

Przepraszam, ale.. a o którą funkcję Eulera chodzi, bo jest zdaje sie kilka takowych.....?

[Barts20]

Korzystałerm z definicji zawartej na wikipedii czyli liczba elentów mniejszych od danej , wzglednie pierwszych z nia

no ja tak rozumiem funkcje eulera

chyba ze nie zrozumialem pytania


chyba że jest kilka funkcji nazywanych "funkcją eulera" których ja nie znam
albo chodziło Ci o cos innego

[juzef]

Czy Twój program potrafi policzyć \(\displaystyle{ \phi(1000000000)}\)?

[Barts20]

zaraz zrobie poprawki bo jest kilka rzeczy które mozna zmienic i powinienem, nie jest problem by obliczyl z wartosc z duzych liczb ale problem jest by zapisac te liczby w tablicy tutaj masz tablice na 1000 elemntów jesli wartosc funkcji jest wieksza niz 1000 program zapisuje na slepo w pamieci i moze ci te wartosc znisczyc i zwrócic zla wartosc, zaraz spróbuje tak wiec nie jest problemem by program liczyl wartosci z duzych liczb (moze nie dowolnie duzych-max to tyle ile potrafi przechowac typ unsigned long która powinien byc tu zamiast int) ale by je zapisal (ale jak powidziałem dynamiczna alkokacja tablicy powinna załawic sprawe)

mozna jescze zwikszyc zakres przechowujac cyfry danej liczby w tablicy znaczy sie jesli mamy np tablice na 1000elemntów to tyle jest cyfr ale to juz jest troche roboty


i zamiścilem wersje poprawioną , dziala, ale dla duzych liczb program nie jest zbyt wydajny, mozna by zwiekszyć jego wydanaść by on te liczby wzglednie pirwsze zapisywal odzielnie znaczy sie bo program jednoczsnie nam zapsuje liczbe liczb wzglednie pierwszych oraz te liczby a funkcja eulera to tylko liczba tych liczb a my robimy dwie czynnsci naraz , jednak mysle ze na predkosc ma najwiekszy wplyw sam algorytm NWD nie wiem mozliwe ze mozna znalezc jescze szybsza jego forme(o ile istnieje) , bo ten ma chyba zlozonosc kwadrtratową.

ewntualnie idzie zrobic jakies inne sztuczki które by zwiekszyły wydajnosc ale to juz przebudowa calego algorytmu)-tak mi sie wydaje

sprawdzilem program zachouje sensowna wydajnasc dla max n=10mln przy n=1mld obliczenie trwa zbyt dlugo a przy wiecej niz \(\displaystyle{ 10^{10}}\)nie pozwala nam na to dany typ i trzeba by kombinowac z zapisen w tablicy ale to i tak nic nie da jesli nie zwieszylo by sie wydajnasci( o ile da sie znaczaco)