SIEVE OF ERASTOTHENES BASED SPOJ PROBLEMS

PROBLEM LINK:
http://www.spoj.com/problems/PRIME1/
http://www.spoj.com/problems/APS/
http://www.spoj.com/problems/AFS/

Approach is pretty same for all three problems.
Precomputation is needed .
Common approach to problems is initialize them initially to 0 or 1 as per ur choice and sieve it out.

Problem 1: http://www.spoj.com/problems/PRIME1/

Take an array
Mark all the multiples of no. by 1 or 0 
Pseudo Approach::
       1 2 3 4 5 6 7 8 9 10
a[n]   0 0 0 0 0 0 0 0 0 0    ==>>intial
       0 0 0 1 0 1 0 1 1 1    ==>>final
Prime nos.: 2 3 5 7  (marked with 0s)

Problem 2:http://www.spoj.com/problems/APS/

Take two arrays i.e. one for f(n) and the other for a[n]
pre-compute f(n)
marks all multiples of no. with the no.   ex.:  a[2]=2  a[4]=2  a[6]=2  a[8]=2...........................
Pseudo Approach::
           1 2 3 4 5 6 7 8 9 10
  f(n)     0 0 0 0 0 0 0 0 0 0      ==>>initial 
           0 2 3 2 5 2 7 2 3 2      ==>>final
  a[n]     0 0 0 0 0 0 0 0 0 0      ==>>initial
           0 2 5 7 12 14 21..................... ==>> final  

Problem 3:http://www.spoj.com/problems/AFS/ 

Take one array 
pre-compute the sum
add the no. to the multiple of the no.   ex.:     a[2]=1    a[4]=a[4]+2   a[6]=a[6]+2........................
Pseudo Approach::
         1   2    3    4    5   6   7   8   9
f(n)     0   0    0    0    0   0   0   0   0  ==>> initial
         0   1    1    3    1   6   1   7   4  ==>>final
a[n]     0   0    0    0    0   0   0   0   0
         0   1    2    5    6   12  13  20  24..

:) :)