מספר ראשוני המופיע בחזקה

כל מספר טבעי (שלם חיובי) ניתן להצגה יחידה כמכפלה של מספרים ראשוניים בחזקות שונות.

המספר 1 אינו נחשב כראשוני ולכן איננו מתייחסים למכפלות שלו.

7 = 71

9 = 32

819819000 = 23 * 32 * 53 * 72 * 111 * 132

68939809 = 194 * 232


יש לנתח את הפירוק של מספר נתון, ולחלץ מתוכו אך ורק את המספרים הראשוניים שמופיעים בחזקה מסוימת.
בהינתן מספר שלם num המייצג את המספר ומספר שלם target המייצג את החזקה.
יש להדפיס מתוך הפירוק של המספר num למספרים ראשוניים את המספרים הראשוניים שמופיעים בפירוק בחזקה target וכן להחזיר את מספרם.

הניחו שעומדת לרשותכם השיטה nextPrime(int) אשר מקבלת כפרמטר מספר חיובי כלשהו ומחזירה את המספר הראשוני הראשון שגדול ממנו.
לדוגמה, אם נקרא לשיטה nextPrime(3) היא תחזיר את המספר 5, שזהו המספר הראשוני הבא אחרי 3.

השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.

אילוצים:
  • יש להחזיר את מספר הגורמים הראשוניים בפירוק וגם להדפיס אותם.
דוגמה 1:
קלט: 
num = 819819000,
target = 1
פלט: 
11
1

הסבר: יש להדפיס את המספר 11 ולהחזיר את הערך 1, כיוון שהוא המספר היחיד המופיע בחזקת 1 בפירוק לראשוניים של המספר

דוגמה 2:
קלט: 
num = 819819000,
target = 2
פלט: 
3
7
13
3

הסבר: יש להדפיס את המספר 3, 7 ו-13 ולהחזיר את הערך 3, כיוון שהם המספרים המופיעים בחזקת 2 בפירוק לראשוניים של המספר

דוגמה 3:
קלט: 
num = 819819000,
target = 3
פלט: 
2
5
2

הסבר: יש להדפיס את המספר 2 ו-5 ולהחזיר את הערך 2, כיוון שהם המספרים המופיעים בחזקת 3 בפירוק לראשוניים של המספר

דוגמה 4:
קלט: 
num = 68939809,
target = 4
פלט: 
19
1

הסבר: יש להדפיס את המספר 19 ולהחזיר את הערך 1, כיוון שהוא המספר היחיד המופיע בחזקת 4 בפירוק לראשוניים של המספר

דוגמה 5:
קלט: 
num = 360,
target = 2
פלט: 
3
1

הסבר: המספר 360 מתפרק לראשוניים כך: 2^3 * 3^2 * 5^1. רק המספר הראשוני 3 מופיע בחזקת 2, לכן יש להדפיס אותו ולהחזיר 1.

דוגמה 6:
קלט: 
num = 1024,
target = 10
פלט: 
2
1

הסבר: המספר 1024 מתפרק לראשוניים כך: 2^10. רק המספר הראשוני 2 מופיע בפירוק, והוא בחזקת 10 ולא בחזקת 10 לכן יש להדפיס אותו ולהחזיר 1.

דוגמה 7:
קלט: 
num = 9801,
target = 2
פלט: 
11
1

הסבר: המספר 9801 מתפרק לראשוניים כך: 3^4 * 11^2. רק המספר הראשוני 11 מופיע בחזקת 2, לכן יש להדפיס אותו ולהחזיר 1.

דוגמה 8:
קלט: 
num = 6125,
target = 1
פלט: 
0

הסבר: המספר 6125 מתפרק לראשוניים כך: 5^2 * 7^2 * 5^3. אין מספרים ראשוניים שמופיעים בחזקת 1 בפירוק זה, לכן אין להדפיס דבר ויש להחזיר 0.

Loading...
נשמרLn 1, Col 1

קלט:

num = 819819000,
target = 1

הפלט המבוקש:

11
1