إيجاد الأرقام المركبة

Question

لدي مجموعة من الأرقام العشوائية.مجموعة هو في الواقع تحديدها من قبل المستخدم ولكن سوف يكون ما يصل إلى 1000 الاعداد الصحيحه.يتم وضعها في هذا:

vector<int> n

وقيم يتم إدراج مثل هذا:

srand(1);

for (i = 0; i < n; i++)
  v[i] = rand() % n;

أنا إنشاء وظيفة منفصلة للعثور على جميع غير رئيس الوزراء القيم.هنا هو ما لدي الآن, ولكن أنا أعلم أنه خاطئ تماما كما تحصل كل من رئيس الوزراء مركب في هذه السلسلة.

void sieve(vector<int> v, int n)
{
  int i,j;

  for(i = 2; i <= n; i++)
     {
        cout << i << " % ";
        for(j = 0; j <= n; j++)
           {
              if(i % v[j] == 0)
                 cout << v[j] << endl;
           }
     }
}

هذه الطريقة عادة ما عملت عندما كنت مجرد سلسلة من الأرقام من 0-1000, ولكن لا يبدو أن العمل الآن عندما يكون لدي أرقام من أجل والتكرارات.هل هناك أفضل طريقة للعثور على غير الأعداد في ناقلات?أنا يميل إلى مجرد إنشاء ناقلات أخرى ، وملء مع ن أرقام فقط تجد غير يعبي بهذه الطريقة ، ولكن من شأنها أن تكون غير فعالة?

حسنا, منذ مجموعة من 0-1000 أنا أتساءل إذا كان من السهل أن مجرد إنشاء ناقلات مع 0-n فرز ثم باستخدام غربال لإيجاد الأعداد الأولية ، هو الحصول على أقرب ؟

void sieve(vector<int> v, BST<int> t, int n)
{
  vector<int> v_nonPrime(n);
  int i,j;
  for(i = 2; i < n; i++)
      v_nonPrime[i] = i;

  for(i = 2; i < n; i++)
     {

        for(j = i + 1; j < n; j++)
           {
              if(v_nonPrime[i] % j == 0)
                 cout << v_nonPrime[i] << endl;
           }
     }
}

Answer 1

في هذا الرمز:

if(i % v[j] == 0)
  cout << v[j] << endl;

وكنت اختبار مؤشر لمعرفة ما إذا كان يقبل القسمة التي كتبها v [ي]. أعتقد أنك من المفترض أن تفعل ذلك على العكس من ذلك، أي بمعنى:.

if(v[j] % i == 0)

والآن، كنت تطبع المقسومات عشوائية من ط. لا تطبع من الأرقام العشوائية التي لا يعرف أن يكون رئيس الوزراء. أيضا، سيكون لديك مكررة في الإخراج، ولعل هذا ما يرام.

Answer 2

أولا، أعتقد قال كانوث لأول مرة: من السابق لأوانه الأمثل هو سبب العديد من الأخطاء. جعل النسخة بطيئة أولا، ثم معرفة كيفية جعلها أسرع.

وثانيا، لحلقة الخاص الخارجي، كنت حقا بحاجة فقط للذهاب الى الجذر التربيعي (ن) بدلا من ن.

Answer 3

وأساسا، لديك الكثير من الأرقام لا علاقة لها، وذلك لكل واحد سيكون لديك لمعرفة ما اذا كان هو رئيس الوزراء.

إذا كنت تعرف مجموعة من الأرقام في وقت مبكر، يمكنك توليد جميع الأعداد الأولية أن <م> يمكن تحدث في هذا النطاق (أو الجذر التربيعي منها)، واختبار كل عدد في حاوية للحصول على القسمة التي كتبها أي واحد من الأعداد الأولية التي تم إنشاؤها.

وتوليد الأعداد الأولية من الأفضل القيام بها Erathostenes المنخل - العديد من الأمثلة التي يمكن العثور عليها في تلك الخوارزمية

Answer 4

ويجب عليك أن تحاول استخدام غربال رئيس الوزراء . عليك أن تعرف عدد القصوى لخلق غربال (O(n)) وبعد ذلك يمكنك بناء مجموعة من الأعداد الأولية في هذا النطاق (O(max_element) أو O(1000) == O(1) الدول مشكلة)) وتحقق ما إذا كان كل عدد هو في مجموعة من الأعداد الأولية.

Answer 5

والتعليمات البرمجية الخاصة بك هو مجرد خطأ. أولا، كنت اختبار ط٪ ضد [ي] == 0، وهو الوراء ويفسر لماذا تحصل جميع الأرقام أيضا. ثانيا، سوف الإخراج الخاص بك يحتوي على التكرارات كما كنت اختبار وإخراج كل عدد المدخلات في كل مرة يفشل في (كسر) اختبار القسمة.

واقتراحات أخرى:

وعن طريق ن كقيمة قصوى في ناقلات وعدد من العناصر في ناقلات مربكة وغير المجدي. أنت لا تحتاج إلى تمرير في عدد من العناصر في ناقلات - كنت مجرد الاستعلام حجم متجه ل. ويمكنك معرفة الحد الأقصى بسرعة إلى حد ما (ولكن إذا كنت تعرف عليه في وقت سابق قد تمر كذلك في).

وكما ذكر أعلاه، تحتاج فقط إلى اختبار لالجذر التربيعي (ن) [حيث n هو قيمة الحد الأقصى في vecotr]

هل يمكن استخدام منخل لتوليد كل يعبي يصل إلى n وبعد ذلك فقط إزالة تلك القيم من ناقلات المدخلات، كما اقترح أيضا أعلاه. وهذا قد يكون أسرع وأسهل للفهم، وخاصة إذا قمت بتخزين الأعداد الأولية في مكان ما.

إذا كنت تريد الذهاب لاختبار كل عدد فردي (باستخدام، أعتقد، وغربال معكوس) ثم أقترح اختبار كل رقم على حدة، في النظام. IMHO أنه سوف يكون من الأسهل فهم من الطريقة التي قمت مكتوب - اختبار كل عدد لالقسمة التي كتبها k <ن لزيادة من أي وقت مضى ك

Answer 6

وفكرة غربال الذي حاولت تنفيذ تعتمد على حقيقة أن تبدأ في مقتبل (2) وشطب الجموع من هذا العدد - لذلك كل الأرقام التي تعتمد على رئيس الوزراء "2" واستبعد مسبقا.

وذلك لأن كل غير يعبي-يمكن factorized الى يعبي. في حين يعبي ليست قسمة مع مودولو 0 إلا إذا كنت تفرق بينهما بنسبة 1 أو من تلقاء نفسها.

وهكذا، إذا كنت ترغب في الاعتماد على هذه الخوارزمية، وسوف تحتاج بعض يعني لاستعادة فعلا هذا العقار من الخوارزمية.

Answer 7

التعليمات البرمجية الخاصة بك ويبدو أن العديد من المشاكل:

1. إذا كنت ترغب في اختبار إذا كان رقمك رئيس الوزراء أو غير رئيس الوزراء ، سوف تحتاج إلى التحقق v[ي] % i == 0, وليس العكس
2. لم تحقق إذا كان لديك عدد يقسم من قبل نفسه
3. يمكنك الحفاظ على التحقق من الأرقام الخاصة بك مرة أخرى ومرة أخرى.هذا هو فعالة جدا.

مثل غيرها من الرجال اقترح عليك أن تفعل شيئا مثل غربال إراتوستينس.

حتى الزائفة ج كود الخاص بك المشكلة (لم تشغيل هذا من خلال المجمعين بعد لذا يرجى تجاهل أخطاء في بناء الجملة.هذا الرمز هو لتوضيح الخوارزمية فقط)

vector<int> inputNumbers;

// First, find all the prime numbers from 1 to n
bool isPrime[n+1] = {true};
isPrime[0]= false;
isPrime[1]= false;
for (int i = 2; i <= sqrt(n); i++)
{
  if (!isPrime[i])
    continue;
  for (int j = 2; j <= n/i; j++)
    isPrime[i*j] = false;
}

// Check the input array for non-prime numbers
for (int i = 0; i < inputNumbers.size(); i++)
{
   int thisNumber = inputNumbers[i];
   // Vet the input to make sure we won't blow our isPrime array
   if ((0<= thisNumber) && (thisNumber <=n))
   {
      // Prints out non-prime numbers
      if (!isPrime[thisNumber])
         cout<< thisNumber;
   }
}

Answer 8

وفرز عدد أولا قد يكون بداية جيدة - يمكنك أن تفعل ذلك في الوقت nLogN. الذي يعد إضافة صغيرة (على ما أظن) لمشكلة الأخرى الخاصة بك - أن العثور على إذا كان الرقم رئيس
. (في الواقع، مع مجموعة صغيرة من الأرقام التي يمكنك القيام به نوعا أسرع بكثير مع نسخة من حجم ناقلات / مجموعة والقيام نوع التجزئة / دلو / أيا كان)

وكنت ثم العثور على أكبر عدد في المجموعة (أفترض الأرقام يمكن أن يكون غير محدود - لا تعرف الحد الأعلى حتى الفرز الخاص بك - أو القيام بتمريرة واحدة للعثور على حد أقصى)

وثم انتقل مع غربال - كما قال آخرون

Answer 9

وجيريمي هو الحق، والمشكلة الأساسية هي i % v[j] بدلا من v[j] % i.

وجرب هذا:

void sieve(vector<int> v, int n) {
  int i,j;

  for(j = 0; j <= n; j++) {
    cout << v[j] << ": ";

    for(i = 2; i < v[j]; i++) {
      if(v[j] % i == 0) {
        cout << "is divisible by " << i << endl;
        break;
      }
    }

    if (i == v[j]) {
      cout << "is prime." << endl;
    }
  }
}

وانها ليست الأمثل، لأنها محاولة لتقسيم جميع الأرقام أقل من v[j] بدلا من مجرد تصل إلى الجذر التربيعي لv[j]. وتحاول dividion جميع أرقام بدلا من الأعداد الأولية فقط.

ولكن هل ستنجح.