[数据结构与算法]聪明的燕姿 搜索dfs 约数之和 java

城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。

可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！

燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字 S，那么自己等的人手上的号码牌数字的所有正约数之和必定等于 S。

所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）。

可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。

输入格式
输入包含 k 组数据。

对于每组数据，输入包含一个号码牌 S。

输出格式
对于每组数据，输出有两行。

第一行包含一个整数 m，表示有 m 个等的人。

第二行包含相应的 m 个数，表示所有等的人的号码牌。

注意：你输出的号码牌必须按照升序排列。

数据范围
1≤k≤100,
1≤S≤2×109
输入样例：
42
输出样例：
3
20 26 41

import java.util.*;

public class Main
{
	static int N=50000,len;
	
	static int prime[]=new int [N],cnt;
	static boolean st[]=new boolean [N];
	
	static int a[]=new int [N];
	
	static boolean is_prime(int x)
	{
		if(x<N)return !st[x];
		for(int i=0;prime[i]<=x/prime[i];++i)
			if(x%prime[i]==0)return false;
		return true;
	}
	
	static void dfs(int last, int prod, int s)
	{
		if(s==1)
		{
			a[len++]=prod;
			return ;
		}
		if(s-1>(last==-1?1:prime[last])&&is_prime(s-1))dfs(s-1,prod*(s-1),1);
		
		for(int i=last+1;prime[i]<=s/prime[i];++i)
		{
			 int p=prime[i];
			 for(int j=p+1,t=p;j<=s;t*=p,j+=t)
			 {
				 if(s%j==0)
				 {
					 dfs(i,prod*t,s/j);
				 }
			 }
		}
		
	}
	
	static void getp(int n)
	{
		for(int i=2;i<=n;++i)
		{
			if(st[i]==false)prime[cnt++]=i;
			for(int j=0;prime[j]*i<=n;++j)
			{
				st[prime[j]*i]=true;
				if(i%prime[j]==0)break;
			}
		}
	}
	
	public static void main(String args[])
	{
		Scanner sc=new Scanner(System.in);
		getp(N-1);
		while(sc.hasNext())
		{
			int s;
			len=0;
			s=sc.nextInt();
			dfs(-1,1,s);
			System.out.println(len);
			Arrays.sort(a,0,len);
			for(int i=0;i<len;++i)System.out.print(a[i]+" ");
			if(len!=0)System.out.println();
		}

	}
}