المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر
دنبال کنندگان ۳ نفر
این وبلاگ را دنبال کنید

سوال دهم Project Euler (همراه راه حل)

چهارشنبه, ۷ فروردين ۱۳۹۲، ۰۱:۲۶ ب.ظ

متن سوال:

مجموع اعداد اول کوچکتر از 10برابر است با 17=7+5+3+2

مجموع اعداد اول کوچکتر از دو میلون چند است؟

پاسخ:

این سوال رو می تونیم  با  روش غربال اراتستن حل کنیم.الگوریتم این غربال بدین گونه است:

1-لیستی از اعداد 2 تا n را ایجاد می کنیم.

2-عددpرو به عنوان اولین عدد اول تعین می کنیم.p=2

3-تمام مضرب های p را از لیست حذف می کنیم.

4-pرا برابر با عدد بعدی در لیست قرار می دهیم که حذف نشده است.

5-مراحل 3 و 4 را تا آنجایی ادامه می دهیم که p*p>n شود.

7-تمام اعدادی که حذف نشده اند اول هستند.

خوب کار ما این است که فقط p ها را با هم جمع کنیم.خیلی راحت.

سورس کامل:

کد!!

نظرات (۱)

سلام من یه سوال داشتم تو یه ازمونی که خوندم سئوالش این بود...
در غربال اراتستن 1 تا 100 بعد از 25 اولین عددی که خط خواهد خورد چه عددی است؟
من اول زدم 30 ولی تو پاسخ نامه زده بود 35....میشه لطفا دلیلش رو بهم بگین که چرا میشه 35؟؟؟؟؟لطفا دلیلش رو به ایمیلم بفرستین....من هفته دیگه ازمون دارم
پاسخ:
سلام
در جواب سوال شما:ببینید 25 فقط بر 5 بخشپذیره پس ما داشتیم مضارب 5 رو خط می زدیم.بعد از 25 عدد 30 اولین مضربه ولی از طرفی قبلا در مضارب 2 خط خورده پس دیگه خط نمی خوره بعدی 35 هست که تا حالا خط نخورده پس جواب 35 هست.
ممنون از اینکه نظر دادید.

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی