كيف استخرج الاعداد الاوليه

فرجت وكنت اضنها لاتفرج :rolleyes:

شكلي انا صاحيه بروحي الصبح

ولأني حلفت ماانام الا لما ارضي ضميري

فتحت كتاب C++

ولقيت برنامج يأدي نفس الغرض ...لا ومشروح كمان :unsure:

بلييييييييييييييييز لاتضحكون علي

وراح احط البرنامج هنا لأي باحث يبي يعرف كيف تطلع الاعداد الاوليه (مااضن في احد يبغى) بس مو مشكله.

#include <iostream>
using namespace std;

int main(){

	int num1;
	int num2,num3;


	cin >> num1;


	for(num2 =2;num2<num1;num2++){
  for(num3=2; num3<= (num2/num3);num3++)
 	 if(!(num2%num3)) break;
 	 if(num3 >(num2/num3))
    cout << num2 << " ";
	}

	return 0;

}

عالعموم اسفة على الازعاج

اختكم لمى

هذا أحد الأمثلة الرائعـة يقوم بعرض الأرقام من 2 إلى 1023 الأولية منها فقط ؛ ثم يطلب من المستخدم إدخال عـدد حتى يختبره إن كان أولياً بشرطا أن يكون أصغر من 1023 ....... إذا لم تفهـمي المثال فستفهمينـه لاحقاً إذا عرفت مكتبة القوالب القياسية std ؛ مصدر المثال مكتوب في آخر الكـود:

// Fig. 23.40: Fig23_40.cpp                                
// Using a bitset to demonstrate the Sieve of Eratosthenes.
#include <iostream>
using std::cin;
using std::cout;
using std::endl;

#include <iomanip>
using std::setw;

#include <cmath> 
using std::sqrt; // sqrt prototype

#include <bitset> // bitset class definition

int main()
{
   const int SIZE = 1024;
   int value;
   std::bitset< SIZE > sieve; // create bitset of 1024 bits
   sieve.flip(); // flip all bits in bitset sieve
   sieve.reset( 0 ); // reset first bit (number 0)         
   sieve.reset( 1 ); // reset second bit (number 1)        

   // perform Sieve of Eratosthenes
   int finalBit = sqrt( static_cast< double > ( sieve.size() ) ) + 1;

   // determine all prime numbers from 2 to 1024
   for ( int i = 2; i < finalBit; i++ )
   {
      if ( sieve.test( i ) ) // bit i is on
      {
         for ( int j = 2 * i; j < SIZE; j += i ) 
            sieve.reset( j ); // set bit j off
      } // end if
   } // end for

   cout << "The prime numbers in the range 2 to 1023 are:\n";

   // display prime numbers in range 2-1023
   for ( int k = 2, counter = 1; k < SIZE; k++ )
   {
      if ( sieve.test( k ) ) // bit k is on
      {
         cout << setw( 5 ) << k;

         if ( counter++ % 12 == 0 ) // counter is a multiple of 12
            cout << '\n';
      } // end if          
   } // end for    
   
   cout << endl;

   // get value from user 
   cout << "\nEnter a value from 2 to 1023 (-1 to end): ";
   cin >> value;

   // determine whether user input is prime
   while ( value != -1 ) 
   {
      if ( sieve[ value ] ) // prime number
         cout << value << " is a prime number\n";
      else // not a prime number
         cout << value << " is not a prime number\n";
      
      cout << "\nEnter a value from 2 to 1023 (-1 to end): ";
      cin >> value;
   } // end while

   return 0;
} // end main

/**************************************************************************
 * (C) Copyright 1992-2005 by Deitel & Associates, Inc. and               *
 * Pearson Education, Inc. All Rights Reserved.                           *
 *                                                                        *
 * DISCLAIMER: The authors and publisher of this book have used their     *
 * best efforts in preparing the book. These efforts include the          *
 * development, research, and testing of the theories and programs        *
 * to determine their effectiveness. The authors and publisher make       *
 * no warranty of any kind, expressed or implied, with regard to these    *
 * programs or to the documentation contained in these books. The authors *
 * and publisher shall not be liable in any event for incidental or       *
 * consequential damages in connection with, or arising out of, the       *
 * furnishing, performance, or use of these programs.                     *
 **************************************************************************/

بالنسبة للكود الأخير فيوجد Optimization بسيط و هو نتيجة حقيقة رياضية سأحاول شرحها

بافتراض الأرقام من 1 الى 10 ( 1 2 3 4 5 6 7 8 9 10 )

ثم بدأنا من الرقم 2 باعتباره أول رقم أولي .. فان أول رقم غير أولي يمكن حذفه من القائمة هو 2 * 2 = 4 ثم يليه 2 * 3 و هكذا ....

تصبح القائمة 2 3 5 7 9

ثم نأتي للرقم التالي للرقم 2 - و الذي لم يتم حذفه في العملية السابقة - في القائمة و هو الرقم 3 سنجد أن أول رقم غير أولي لم يتم حذفه من قبل هو 3 * 3 = 9

و تصبح القائمة 2 3 5 7

ثم نأتي للرقم التالي للرقم 3 - و الذي لم يتم حذفه في العملتين السابقتين - في القائمة و سنجد أنه الرقم 5 و سنجد أن أول رقم أولي لم يتم حذفه من قبل هو 5 * 5 = 25 و هو خارج نطاق مجموعة الأعداد من 1 الى 10 و لهذا نوقف العلمية و نبدأ في البحث عن جميع الأعداد غير المحذوفة من القائمة سنجد العدد 7 و لن نحتاج لحذف مضاعفاته أيضاً لأن أول مضاعف للرقم 7 لم يتم حذفه في العمليات السابقة هو 49 و هو أيضاً خارج النطاق و هكذا نجد أن الأعداد الأولية الموجودة هي 2 3 5 7

و هذه هي الخوارزمية المستخدمة في الكود السابق تقريباً فهو يحجز عدد من الBits بمقدار نطاق الأعداد و يقوم بعمل Mark على الأعداد غير الأولية في القائمة و لكنه في هذا الجزء

// determine all prime numbers from 2 to 1024
  for ( int i = 2; i < finalBit; i++ )
  {
     if ( sieve.test( i ) ) // bit i is on
     {
        for ( int j =2 * i; j < SIZE; j += i )
           sieve.reset( j ); // set bit j off
     } // end if
  } // end for

أخطأ خطأً صغيراً فلقد بدأ الloop التي تقوم بعمل Mark على الأعداد من 2 * i و لكن كان من المفترض أن يبدأ من i * i أي تربيع i لأن أول رقم يجب أن يتم حذفه من القائمة هو حاصل ضرب الرقم الأولي في نفسه ثم مضاعفات الرقم

اي أنها كانت يجب أن تكون

// determine all prime numbers from 2 to 1024
  for ( int i = 2; i < finalBit; i++ )
  {
     if ( sieve.test( i ) ) // bit i is on
     {
        for ( int j = i * i; j < SIZE; j += i )
           sieve.reset( j ); // set bit j off
     } // end if
  } // end for

و هذا يوفر بعض اللفات

و أيضاً كان يمكن توفير اللفة الأولى في الloop و هي اللفة التي تحذف الأرقام التي تقبل القسمة على 2 و هي الأرقام الزوجية و هي في الحقيقة نصف الأرقام أي أن أول لفة هي أطول لفة و اختصارها مفيد جداً و بسيط يكفي أن تبدأ الloop من 3 و تجعل العداد يزيد ب 2 بدل 1 و أيضاً اثناء عملية عرض الأرقام يمكن البدء بالرقم 3 و العداد يزيد ب 2

و في النهاية هذا هو الكود بعد عملية الOptimization البسيطة

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

#include <iomanip>
using std::setw;

#include <cmath>
//using std::sqrt; // sqrt prototype

#include <bitset> // bitset class definition

int main()
{
  const int SIZE = 2048;
  int value;
  std::bitset< SIZE > sieve; // create bitset of 1024 bits
  sieve.flip(); // flip all bits in bitset sieve
  sieve.reset( 0 ); // reset first bit (number 0)        
  sieve.reset( 1 ); // reset second bit (number 1)        

  // perform Sieve of Eratosthenes
  int finalBit = sqrt( static_cast< double > ( sieve.size() ) ) + 1;

  // determine all prime numbers from 2 to 1024
  for ( int i = 3; i < finalBit; i+=2 )
  {
     if ( sieve.test( i ) ) // bit i is on
     {
        for ( int j = i * i; j < SIZE; j += i )
           sieve.reset( j ); // set bit j off
     } // end if
  } // end for

  cout << "The prime numbers in the range 2 to 1023 are:\n";

  // display prime numbers in range 2-1023
  cout<< setw(5) << 2;
  for ( int k = 3, counter = 1; k < SIZE; k+=2 )
  {
     if ( sieve.test( k ) ) // bit k is on
     {
        cout << setw( 5 ) << k;

        if ( counter++ % 12 == 0 ) // counter is a multiple of 12
           cout << '\n';
     } // end if          
  } // end for    

  cout << endl;

  // get value from user
  cout << "\nEnter a value from 2 to 1023 (-1 to end): ";
  cin >> value;

  // determine whether user input is prime
    while ( value != -1 )
  {
     if ( (sieve[ value ] && value % 2) || value == 2) // prime number
        cout << value << " is a prime number\n";
     else // not a prime number
        cout << value << " is not a prime number\n";
     
     cout << "\nEnter a value from 2 to 1023 (-1 to end): ";
     cin >> value;
  } // end while

  return 0;
} // end main

شكراً أخي بشمهـندس على التوضيحات

هذا المثال أخذتـه من كتاب C++ How to program ولم أنتبـه لا إلى طريقة إيجاد الأعداد الأولية ولا أي شيء آخر ,,,, وإنما وضعتـه هـكذا للفائدة ... وحتى لو قرأت الكـود فلن أفهـمـه ... على العـموم شكراً على الشرح :D ................

ايه والله شكرا اخوي بشمهندس

صحيح انا مافهمت البرنامج ككل لاني لسا مادرستstd ولا ادري وش هي لكن فهمت logic

يعطيــــــــــــــــــــــــــــــــــــــــــــــك العافيه ماقصرت :)