1.先作出这个数的常规意义下的所有因子,再验证这些因子是否满足特定的素因子的条件.

 

2.用线形筛法筛出可能的素因子,hash或者二分查找.

 

 

#include <iostream>
#include <algorithm>
using namespace std;

int a[300001];
int ans[60000];
void prime(int n)
{
 a[0]=1;
 a[1]=1;
 for(int i=2;i*i<=n;i++)
 {
  if(a[i]==0&&(i%7==1||i%7==6))
  {
   for(int j=i*i;j<=n;j+=i)
   {
    a[j]=1;
   }
  }
 }
}
int factor(int n)
{
 int k=0;
 for(int i=2;i*i<=n;i++)
 {
  if(n%i==0)
  {
   ans[k++]=i;
   if(i!=n/i)
   ans[k++]=n/i;
  }
 }
 ans[k++]=n;
 sort(ans,ans+k);
 return k;
}
int main()
{
 prime(300000);
 int n;
 while(cin >>n)
 {
  if(n==1)
   break;
  else
  {
   cout<<n<<":";
   int x=factor(n);
   for(int i=0;i<x;i++)
   {
    if((ans[i]%7==1||ans[i]%7==6)&&!a[ans[i]])
     cout<<" "<<ans[i];
   }
   cout<<endl;
  }
 }
 return 0;
}