მარტივი რიცხვების ჯამი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: IBSU, 2014, ზამთრის ოლიმპიადა, VII-IX


მოცემულია მთელი დადებითი n რიცხვი. S(n)-ით ავღნიშნოთ იმ გზათა რაოდენობა, რომელთა საშუალებითაც n შეიძლება ჩაიწეროს როგორც ორი ან მეტი მარტივი რიცხვის ჯამი. მაგალითად, S(9)=4, რადგან 9 = 2 + 2 + 2 + 3 = 2 + 2 + 5= 2 + 7 = 3 + 3 + 3. დავუშვათ, p უმცირესი მარტივი რიცხვია, რომელიც მეტია n–ზე. 

დაწერეთ პროგრამა, რომელიც გამოითვლის S(n)-ის p–ზე გაყოფით მიღებულ ნაშთს.

შესატანი მონაცემები: სტანდარტული შეტანის ერთადერთ სტრიქონში მოცემულია ერთი მთელი დადებითი n რიცხვი (n < 50 000).

გამოსატანი მონაცემები: სტანდარტული გამოტანის ერთადერთ სტრიქონში უნდა ჩაიწეროს S(n)-ის p–ზე გაყოფით მიღებული ნაშთი.




მაგალითები

შესატანი მონაცემები
9 დაკოპირება
გამოსატანი მონაცემები
4 დაკოპირება