113 - Nearly prime numbers
سه شنبه, ۲ دی ۱۳۹۳، ۰۵:۳۰ ب.ظ
مفهوم سوال
عدد X رو Nearly prime number میگیم هرگاه بشه عدد X رو به صورت P1 * P2 نوشت.
سوال به ما N عدد میده و می خواد بررسی کنیم که کدومشون nearly prime هستش.
X < 109
حل
اگه خوب دقت کنید میبینید که تنها اعدادی که 2 عامل اول دارند nearly prime هستند. پس فقط کافیه تعداد عوامل اول اعداد ورودی رو بشماریم.
از اونجایی که اگر X اول نباشه، عوامل اولش همه از (sqrt(109 کوچکتر هستند، کافیه همه اعداد اول تا 105 رو بدست بیاریم و بعدش جواب هر تست رو بدست بیاریم.
