به یه عدد میگیم «تقریبن اول» اگه برابر حاصل ضرب دو تا عدد اول باشه. توی ورودی n رو بهتون میده و توی خط بعدش n تا عدد میده. توی خروجی باید n خط شامل Yes/No چاپ کنید. توی خط iام بنویسید Yes اگر عدد iام ورودی تقریبن اول بود و در غیر این صورت بنویسید No. N ≤ 10 Ai ≤ 10^9
یه راه حلوندن این سوال بک ترک زدن با باند و برنچ خوبه. خیلی خوب میشه تایمش اگه باند و برنچ خوبی بزنی!
2015-04-27 09:46:36 -0600 م زمانیسلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 07:11:15 -0600 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 06:27:12 -0600 امیر شکریاول با غربال تمام اعداد اول 1 تا رادیکال r=1000000000 رو به دست میاریم. بعدش اعدادو می گیریم. به ازای هر عدد a اگه اول نباشه حتما یه مقسوم علیه زیر r داره و اگه بشه به صورت حاصلضرب دو عدد اول نوشتش حتما یکیش زیر r هست. اونو پیدا می کنیم با حدود 3000 عملیات (تا r حدود 3000 عدد اول پیدا میشه.). بعدش اون عددو بر r تقسیم میکنیم وبا حدود 3000 عملیات دیگه می فهمیم که اون عدد اول هست یا نه. بعدش اگه اول بود میشه عدد a رو به صورت حاصلضرب دو عدد اول نوشت وگرنه نمی شه.
پس با حداکثر 9000000 عملیات به جواب می رسیم که 10 تاش میشه 90000000 که زیر 1 ثانیه run میشه.
چرا اینقدره پیچوندی ؟ برای چک هر عدد ده به توان پنج تا عملیات لازمه (تا رادیکال اون عدد رو چک میکنیم) که ضربدر دهش میشه ده به توان شیش .
2015-04-29 12:26:11 -0600 سماق دو