Fitness computation after each crossover or mutation operation in Genetic Algorithm (GA) requires computational time that increases with the increasing length of the chromosome. In this paper, an efficient GA is proposed for protein folding prediction based on the Hydrophobic-Hydrophilic (HP) model. The partial fitness of the parent computed from one end of sequence till crossover or mutation point is utilized for the computation of the fitness of the child. The calculated value of the partial fitness is stored with the corresponding chromosome. Although the approach requires additional memory for each hydrophobic residue of each chromosome, the computation time is reduced significantly which is more important than the memory overhead.