برنامج الأعداد الأولية
https://stackoverflow.com/questions/502443
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أقوم حاليًا بتجربة بعض الأسئلة فقط لممارسة مهاراتي في البرمجة.(لم أدرسه في المدرسة أو أي شيء آخر بعد، لقد تعلمت بنفسي) واجهت هذه المشكلة التي تطلبت مني قراءة رقم من ملف txt معين.سيكون هذا الرقم N.الآن أفترض أن أجد العدد الأولي N لـ N <= 10000.وبعد العثور عليه، من المفترض أن أقوم بطباعته إلى ملف txt آخر.الآن بالنسبة لمعظم أجزاء السؤال، فأنا قادر على فهم واستنباط طريقة للحصول على N.المشكلة هي أنني أستخدم مصفوفة لحفظ الأعداد الأولية التي تم العثور عليها مسبقًا وذلك لاستخدامها للتحقق من الأرقام المستقبلية.حتى عندما كان حجم المصفوفة 100، وطالما كان عدد الإدخال الصحيح أقل من 15 تقريبًا، فإن البرنامج يتعطل.
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
int main() {
ifstream trial;
trial.open("C:\\Users\\User\\Documents\\trial.txt");
int prime;
trial >> prime;
ofstream write;
write.open("C:\\Users\\User\\Documents\\answer.txt");
int num[100], b, c, e;
bool check;
b = 0;
switch (prime) {
case 1:
{
write << 2 << endl;
break;
}
case 2:
{
write << 3 << endl;
break;
}
case 3:
{
write << 5 << endl;
break;
}
case 4:
{
write << 7 << endl;
break;
}
default:
{
for (int a = 10; a <= 1000000; a++) {
check = false;
if (((a % 2) != 0) && ((a % 3) != 0) && ((a % 5) != 0) && ((a % 7) != 0)) // first filter
{
for (int d = 0; d <= b; d++) {
c = num[d];
if ((a % c) == 0) {
check = true; // second filter based on previous recorded primes in array
break;
}
}
if (!check) {
e = a;
if (b <= 100) {
num[b] = a;
}
b = b + 1;
}
}
if ((b) == (prime - 4)) {
write << e << endl;
break;
}
}
}
}
trial.close();
write.close();
return 0;
}
لقد قمت بهذا بناءً على دليل الدمى الخاص بي وأنا بنفسي، لذا أسامح بعض عدم كفاءة التعليمات البرمجية والمبتدئ العام في الخوارزمية الخاصة بي.أيضًا لما يصل إلى 15 يعرض الأعداد الأولية بشكل صحيح.
هل يمكن لأحد أن يخبرني كيف يجب علي تحسين هذا الكود الحالي؟أفكر في استخدام ملف txt بدلاً من المصفوفة.هل هذا ممكن؟هو موضع تقدير أي مساعدة.
المحلول 13
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
int main()
{
ifstream trial;
trial.open("C:\\Users\\User\\Documents\\trial.txt");
int prime, e;
trial>>prime;
ofstream write;
write.open("C:\\Users\\User\\Documents\\answer.txt");
int num[10000], currentPrime, c, primePrint;
bool check;
currentPrime=0;
num[currentPrime] = 2;
currentPrime=1;
for(int currentInt=2; currentInt<=1000000; currentInt++)
{check = false;
for( int arrayPrime=0; arrayPrime<currentPrime; arrayPrime++)
{ c=num[arrayPrime];
if ((currentInt%c)==0) { check = true;// second filter based on previous recorded primes in array
break;}
}
if (!check)
{ e=currentInt;
if( currentInt!= 2 ) {
num[currentPrime]= currentInt;}
currentPrime = currentPrime+1;}
if(currentPrime==prime)
{
write<<e<<endl;
break;}
}
trial.close();
write.close();
return 0;
}
وهذا هو الأساس النسخة النهائية على قانون بلدي الأصلي. وهو يعمل تماما وإذا كنت ترغب في زيادة نطاق الأعداد الأولية ببساطة زيادة عدد صفيف. شكرا للمساعدة =)
نصائح أخرى
نظرًا لأن سؤالك يدور حول البرمجة وليس الرياضيات، فسأحاول الاحتفاظ بإجابتي بهذه الطريقة أيضًا.
النظرة الأولى لشفرتك تجعلني أتساءل عما تفعله هنا بحق السماء...إذا قرأت الإجابات، فسوف تدرك أن بعضها لم يكلف نفسه عناء فهم التعليمات البرمجية الخاصة بك، والبعض الآخر يقوم فقط بتفريغ التعليمات البرمجية الخاصة بك إلى مصحح الأخطاء ومعرفة ما يحدث.هل لأننا غير صبورين إلى هذا الحد؟أم أن الأمر ببساطة هو أن الكود الخاص بك يصعب فهمه بحيث لا يمثل مشكلة سهلة نسبيًا؟
لتحسين شفرتك، حاول أن تسأل نفسك بعض الأسئلة:
- ماذا يكون
a,b,c, ، إلخ؟أليس من الأفضل إعطاء أسماء ذات معنى أكثر؟ - ما هي الخوارزمية الخاصة بك بالضبط؟هل يمكنك كتابة فقرة مكتوبة بوضوح باللغة الإنجليزية حول ما تفعله (بطريقة دقيقة)؟هل يمكنك تعديل الفقرة إلى سلسلة من الخطوات التي يمكنك تنفيذها ذهنيًا على أي مدخلات ويمكنك التأكد من صحتها؟
- هل كل الخطوات ضرورية؟هل يمكننا الجمع أو حتى القضاء على بعضها؟
- ما هي الخطوات التي يسهل التعبير عنها باللغة الإنجليزية ولكنها تتطلب، على سبيل المثال، أكثر من 10 أسطر في C/C++؟
- هل تحتوي قائمة الخطوات الخاصة بك على أي هياكل؟الحلقات؟أجزاء كبيرة (ربما متكررة) يمكن وضعها كخطوة واحدة مع خطوات فرعية؟
بعد الانتهاء من الأسئلة، من المحتمل أن يكون لديك رمز زائف واضح المعالم يحل المشكلة، وهو أمر يسهل شرحه وفهمه.بعد ذلك يمكنك تنفيذ الكود الزائف الخاص بك في C/C++، أو في الواقع، أي لغة للأغراض العامة.
هناك طريقتان لاختبار البدائية قد ترغب في أخذهما في الاعتبار:
- مجال المشكلة صغير بما يكفي لدرجة أن مجرد تكرار الأرقام حتى تجد العدد الأولي N قد يكون حلاً مقبولاً ويستغرق إكماله أقل من بضعة أجزاء من الثانية.هناك عدد من التحسينات البسيطة التي يمكنك إجراؤها على هذا الأسلوب، على سبيل المثال، تحتاج فقط إلى الاختبار لمعرفة ما إذا كان قابلاً للقسمة على 2 مرة واحدة ثم ما عليك سوى التحقق من الأرقام الفردية وما عليك سوى التحقق من الأرقام الأقل من أو تساوي إلى الجذر التربيعي للرقم الذي يتم اختباره.
- غربال إراتوستينس فعال للغاية وسهل التنفيذ وخفيف بشكل لا يصدق في نهاية الأمور الحسابية.
أما بالنسبة لسبب تعطل التعليمات البرمجية، فأظن أن تغيير السطر الذي يقرأ
for( int d=0; d<=b; d++)
ل
for( int d=0; d<b; d++)
سيصلح المشكلة لأنك تحاول القراءة من عنصر يحتمل أن يكون غير مهيأ في المصفوفة والذي من المحتمل أن يحتوي على بيانات غير مرغوب فيها.
وأنا لم ينظر في التعليمات البرمجية الخاصة بك، ولكن يجب أن يكون لديك مجموعة كبيرة بما يكفي لاحتواء كل القيم التي سوف تخزن في ذلك. 100 بالتأكيد لن يكون كافيا بالنسبة لمعظم المدخلات لهذه المشكلة.
ومنها مثلا. هذا الرمز ..
int someArray[100];
someArray[150] = 10;
ويكتب إلى موقع كبير من مجموعة (150> 100). وهذا ما يعرف في الكتابة الذاكرة. اعتمادا على ما حدث ليكون في ذلك الموقع الذاكرة قد يتلف البرنامج على الفور، في وقت لاحق، أو أبدا على الإطلاق.
ومن الممارسات الجيدة عند استخدام المصفوفات هو تأكيد في بطريقة ما أن العنصر الذي يتم الكتابة إلى هو في حدود المصفوفة. أو استخدام فئة مجموعة من نوع أن يؤدي هذا التحقق.
لمشكلتك النهج سيكون أسهل لاستخدام فئة ناقلات STL. في حين يجب إضافة العناصر (ناقلات :: push_back ()) يمكنك في وقت لاحق عناصر الوصول باستخدام المشغل مجموعة []. سوف ناقلات يوفر لك أفضل أداء تكرارية.
وإليك بعض التعليمات البرمجية لإضافة الأرقام 0-100 إلى ناقل ومن ثم طباعتها. ملاحظة في الحلقة الثانية التي نستخدمها عدد من العناصر المخزنة في ناقلات.
#include <vector> // std::vector
...
const int MAX_ITEMS = 100;
std::vector<int> intVector;
intVector.reserve(MAX_ITEMS); // allocates all memory up-front
// add items
for (int i = 0; i < MAX_ITEMS; i++)
{
intVector.push_back(i); // this is how you add a value to a vector;
}
// print them
for (int i = 0; i < intVector.size(); i++)
{
int elem = intVector[i]; // this access the item at index 'i'
printf("element %d is %d\n", i, elem);
}
وأنا أحاول تحسين البرمجة الوظيفية لي في الوقت الراهن لذلك أنا فقط مشفرة حتى غربال بسرعة. الرقم الأول سوف ظيفة هنا. إذا كنت لا تزال التعلم، قد تجد أنه من المثير أيضا.
#include <iostream>
#include <list>
#include <math.h>
#include <functional>
#include <algorithm>
using namespace std;
class is_multiple : public binary_function<int, int, bool>
{
public:
bool operator()(int value, int test) const
{
if(value == test) // do not remove the first value
return false;
else
return (value % test) == 0;
}
};
int main()
{
list<int> numbersToTest;
int input = 500;
// add all numbers to list
for(int x = 1; x < input; x++)
numbersToTest.push_back(x);
// starting at 2 go through the list and remove all multiples until you reach the squareroot
// of the last element in the list
for(list<int>::iterator itr = ++numbersToTest.begin(); *itr < sqrt((float) input); itr++)
{
int tmp = *itr;
numbersToTest.remove_if(bind2nd(is_multiple(), *itr));
itr = find(numbersToTest.begin(), numbersToTest.end(), tmp); //remove_if invalidates iterator
// so find it again. kind of ugly
}
// output primes
for(list<int>::iterator itr = numbersToTest.begin(); itr != --numbersToTest.end(); itr++)
cout << *itr << "\t";
system("PAUSE");
return 0;
}
وأي نصيحة حول كيفية تحسين هذا سيكون موضع ترحيب من جانب الطريق.
وهنا هو رمز بلادي. عند العمل على عدد كبير، انها بطيئة جدا! ويمكن حساب كل الأعداد الأولية مع عدد يمكنك إدخال!
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int main()
{
int m;
int n=0;
char ch;
fstream fp;
cout<<"What prime numbers do you want get within? ";
if((cin>>m)==0)
{
cout<<"Bad input! Please try again!\n";
return 1;
}
if(m<2)
{
cout<<"There are no prime numbers within "<<m<<endl;
return 0;
}
else if(m==2)
{
fp.open("prime.txt",ios::in|ios::out|ios::trunc);//create a file can be writen and read. If the file exist, it will be overwriten.
fp<<"There are only 1 prime number within 2.\n";
fp<<"2\n";
fp.close();
cout<<"Congratulations! It has worked out!\n";
return 0;
}
else
{
int j;
int sq;
fp.open("prime.txt",ios::in|ios::out|ios::trunc);
fp<<"2\t\t";
n++;
for(int i=3;i<=m;i+=2)
{
sq=static_cast<int>(sqrt(i))+1;
fp.seekg(0,ios::beg);
fp>>j;
for(;j<sq;)
{
if(i%j==0)
{
break;
}
else
{
if((fp>>j)==NULL)
{
j=3;
}
}
}
if(j>=sq)
{
fp.seekg(0,ios::end);
fp<<i<<"\t\t";
n++;
if(n%4==0)
fp<<'\n';
}
}
fp.seekg(0,ios::end);
fp<<"\nThere are "<<n<<" prime number within "<<m<<".\n";
fp.close();
cout<<"Congratulations! It has worked out!\n";
return 0;
}
}
لواحد، وكنت قد أقل رمز (والذي هو دائما شيء جيد!) إذا لم يكن لديك حالات خاصة لمدة 3 و 5 و 7.
وبالإضافة إلى ذلك، يمكنك تجنب حالة خاصة بالنسبة لل2 إذا كنت مجرد مجموعة الأسطوانات [ب] = 2 والاختبار الوحيد للالقسمة من الأشياء في مجموعة الخاصة بك.
ويبدو كما تذهب في جميع أنحاء ل() حلقة رئيسية، وقيمة زيادات ب.
وبعد ذلك، وهذا يؤدي في حادث تحطم طائرة لأنك الوصول إلى ذاكرة قبالة نهاية الصفيف الخاص بك:
for (int d = 0; d <= b; d++) {
c = num[d];
وأعتقد أنك بحاجة للحصول على خوارزمية أكثر وضوحا في رأسك ثم الاقتراب من الرمز مرة أخرى.
وتشغيل التعليمات البرمجية الخاصة بك من خلال المصحح، لقد وجدت أنه تعطل مع عائم استثناء نقطة في "if ((a % c) == 0)". والسبب في ذلك هو أن لديك لم يتم تهيئة أي شيء في الأسطوانات، حتى تفعلونه "ل٪ 0".
ومن ما أعرفه، في C / C ++ كثافة العمليات هو نوع 16bit وبالتالي لا يمكن أن يصلح 1000000 في ذلك (الحد الأقصى هو 2 ^ 16 = 32K). محاولة لإعلان "أ" طالما
وأعتقد أن يقول معيار C التي int على الأقل كبير مثل short وعلى الأكثر كبيرة مثل long.
في int الممارسة هو 4 بايت، لذلك يمكن أن تعقد الأرقام بين -2^31 و2^31-1.
وبما أن هذا هو لأغراض تربوية، أود أن أقترح تنفيذ منخل من إراتوستينس .
وهذا ينبغي أن تكون ذات فائدة لك: http://en.wikipedia.org/wiki/ Primality_test
for(int currentInt=2; currentInt<=1000000; currentInt++)
{check = false; // Basically the idea for this for loop is to run checks against integers. This is the main for loop in this program. I re initialize check to false ( check is a bool declared above this. )
for( int arrayPrime=0; arrayPrime<currentPrime; arrayPrime++) // This for loop is used for checking the currentInt against previously found primes which are stored in the num array.
{ c=num[arrayPrime];
if ((currentInt%c)==0) { check = true;// second filter based on previous recorded primes in array
break;} // this is the check. I check the number against every stored value in the num array. If it's divisible by any of them, then bool check is set to true.
if ( currentInt == 2)
{ check = false; } // since i preset num[0] = 2 i make an exception for the number 2.
if (!check)
{
e=a;
if(currentPrime <= 100){
num[currentPrime]= currentInt;} // This if uses check to see if the currentInt is a prime.
currentPrime = currentPrime+1;} // increases the value of currentPrime ( previously b ) by one if !check.
if(currentPrime==prime)
{
write<<e<<endl;
break;} // if currentPrime == prime then write the currentInt into a txt file and break loop, ending the program.
وشكرا على النصيحة polythinker =)
ومنذ ستحتاج القيم عدد أولي أكبر لل الأسئلة في وقت لاحق ، I أقترح عليك اتباع dreeves المشورة، والقيام غربال. وهو السهم من المفيد جدا أن يكون في جعبة الخاص بك.
