اريد شرح عن تمارين prime number في c++

قواسم عدد صحيح :

نقول أن عدد صحيح b يقسم العدد الصحيح a إذا وفقط إذا وجد عدد صحيح k بحيث

a = b * k

خصائص قواسم عدد :

حسب تعريف قاسم عدد ، نفترض في هذا أنa و b عددين غير منعدمين إذن k أيضا غير منعدم

a = b * k
| a | = | b * k |
| a | = | b | * | k |
| a | / | b | = | k |
| a | / | b | = | k | > 0
| a | / | b | = | k | >= 1
| a | / | b | >= 1
| a | >= | b |
| a | >= b >= -| a |

1. إذن جميع القواسم b للعدد a محصورة بين a و -a
2. أيضا إذا كان b يقسم a فإن -b يقسم a ومنه فإن القواسم الموجبة تماثلها قواسم أخرى سالبة
3. العدد 1 قاسم لجميع الأعداد الصحيحة
4. العدد a قاسم للعدد a

نستنتج أن قواسم العدد الموجبة محصورة بن 1 و a

العدد الأولي :

هو كل عدد صحيح له 4 قواسم مختلفة فقط

وحسب خصائص قواسم العدد فإنه كل عدد صحيح له قاسمين موجبين مختلفين فقط هما 1 و a

مما يعني أنه إذا وجد قاسم آخر غير 1 و a فإن العدد غير أولي

---

من كل ما سبق نستنتج أنه لفحص عدد هل هو أولي يجب فحص جميع الأعداد المحصورة بين 1 و a ويجب ألا تكون قواسم للعدد a

function isPrime(a) {
    if (a === 0 || a === 1) {return false; }
    if (a < 0) {return isPrime(-a); }
    var b;
    for (b = 2; b < a; b += 1) {
        if (a % b === 0) {return false; }
    }
    return true;
}

حسنا تعقيد هذه الخوارزمية هو (O(n لكن يمكن جعلها ((O(sqrt(n طبعا ببرهان أنه يكفي التحقق من الأعداد الأصغر من الجذر التربيعي ل a

function isPrime(a) {
    if (a === 0 || a === 1) {return false; }
    if (a < 0) {return isPrime(-a); }
    var b, sqrtA = Math.sqrt(a);
    for (b = 2; b <= sqrtA; b += 1) {
        if (a % b === 0) {return false; }
    }
    return true;
}