noip2012普及组——质因数分解

 1 #include<stdio.h>
 2 #include<math.h>
 3 int fun(int p);
 4 int main()
 5 {
 6     int n,t,i,flag=0;
 7     long a,b;
 8 
 9     scanf("%d",&n);
10     t=n/2;
11     for(i=t;i>=2;i--)
12     {
13         if(n%i==0)//i是n的约数
14         {
15             if(fun(i)==1&&fun(n/i) )//i是质数而且n/i也是质数
16             {
17                 flag=1;
18                 break;
19             }
20         }
21     }
22     if(flag==1)
23     {
24         printf("%d\n",i);
25     }
26     return 0;
27 }
28 int fun(int p)//判断p是否质数yes返回1no返回0.
29 {
30     int i,t=sqrt(p);
31     for(i=2;i<=t;i++)
32     {
33         if(p%i==0)
34         {
35             return 0;
36         }
37     }
38     return 1;
39 }

 1 #include<iostream> 
 2 #include<cstdio> 
 3 #include<fstream> 
 4 #include<cmath>
 5 
 6 using namespace std;
 7 #define fin cin
 8 #define fout cout
 9 short pr[50000]={0}; 
10 int main() 
11 { 
12     //ifstream fin("prime.in"); 
13     //ofstream fout("prime.out"); 
14     pr[1]=1; 
15     int n,maxi=1; 
16     fin>>n; 
17     for(int i=2;i<=(int)sqrt(n);i++)
18     { 
19         if(pr[i]==0)
20         { 
21             for(int j=i*2;j<=(int)sqrt(n);j+=i)
22             { 
23                 pr[j]=1; 
24             } 
25             if(n%i==0)maxi=n/i; 
26         }
27     }
28     fout<<maxi<<endl; 
29     return 0;
30 }

 1 #include<cstdio> 
 2 #include<iostream> 
 3 using namespace std; 
 4 int n; 
 5 int main()
 6 { 
 7     freopen("prime9.in","r",stdin);
 8     //freopen("output.txt","w",stdout);
 9     scanf("%d",&n); 
10     for(int i=2;i<=44721;i++) if(n%i==0) { cout<<n/i<<endl; break;} 
11     return 0; 
12 }