Description

Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2 + 3 + 5 + 7 + 11 + 13, 11 + 13 + 17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive prime numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20.

[ complete description ] [ A.java ]

Sample Input

2
3
17
41
20
666
12
53
0 

Sample Output

1
1
2
3
0
0
1
2 

Solution

public int[] primes;

public void go() throws Exception
{
	Scanner in = new Scanner(new File("A.txt"));
	int n = in.nextInt();
	getAllPrimes();
	while (n != 0)
	{
		System.out.println(pcount(n));
		n = in.nextInt();
	}
}

public int pcount(int n)
{
	int count = 0, i, j, k;
	for (i = 0; i < primes.length; i++)
	{
		int total = 0;
		for (j = i; j < primes.length && total < n; j++)
		{
			total += primes[j];
		}
		if (total == n)
		{
			count++;
			String e = "";
			for (k = i; k < j; k++)
				e += primes[k] + ", ";
			err(e);
		}
	}
	return count;
}

public void getAllPrimes()
{
	ArrayList<Integer> lprimes = new ArrayList<Integer>();
	for (int i = 2; i < 10000; i++)
	{
		boolean okay = true;
		for (int j = 2; j <= i / 2; j++)
		{
			if (i % j == 0)
			{
				okay = false;
				break;
			}
		}
		if (okay)
		{
			lprimes.add(i);
		}
	}
	primes = new int[lprimes.size()];
	for (int i = 0; i < primes.length; i++)
	{
		primes[i] = ((Integer)lprimes.get(i)).intValue();
	}
}