欧拉函数.cpp

组合数学 中 欧拉函数的 实现 用STL 编写

/************************************************************************/
/*                欧拉函数                                              */
/************************************************************************/
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

class ola
{
public:
	ola():x(x),heshu(0),subi(0){}                                                          
    ~ola(){ delete heshu; delete subi;}
	void sub();
private:
	int x;
	vector<int> * heshu;
	vector<int> * subi;
};

void main()
{	
	ola q;                                 
	q.sub();
}
void ola::sub()
{
	vector<int> * heshu = new vector<int>;
	vector<int> * sub = new vector<int>;
    vector<int>::iterator iter,result,sub_iter,result1;
	ostream_iterator<int> screen(cout," ");
	
    cout<<"Enter a  num:"<<endl;
	cin>>x;
	for (int i=2;i<=x;i++)
	{
		heshu->push_back(i);
	}
    
    iter=heshu->begin();
	while (iter!=heshu->end())
	{
		for (int j=2;j<*iter;j++)
		{
			if ((*iter)%j==0)
			{
				*iter=-1;
				break;
			}
		}
		iter++;
	}
    result1=remove(heshu->begin(),heshu->end(),-1);
	heshu->erase(result1,heshu->end());
	
	//copy(heshu->begin(),heshu->end(),screen);
	//cout<<endl;
    
	iter=heshu->begin();
	int b=x;	
	while (iter!=heshu->end())
	{
			while(b%*iter==0)
			{
                sub->push_back(*iter);
				b=b/(*iter);
			}
		    iter++;
	}
	result=unique(sub->begin(),sub->end());
	sub->erase(result,sub->end());

	cout<<x<<"的因子:"<<endl;
	copy(sub->begin(),sub->end(),screen);
	cout<<endl;

    int sum=x;
	sub_iter=sub->begin();
	while (sub_iter!=sub->end())
	{
		sum=sum*(1.0-(1.0/(*sub_iter)));
		sub_iter++;
	}
	cout<<"欧拉函数:"<<endl;
	cout<<sum<<endl;	  
}