היא מוצאת את המחלק המשותף הגדול ביותר של שני מספרים שלמים.עכשיו נגדיר:
נבטא את p בעזרת a, b, d:
מכיוון ש p הוא שלם אז המונה אמור להתחלק במכנה. נבדוק אילו איברים במונה מתחלקים במכנה:
מכאן ניתן ללמוד כי הביטויים במונה (חוץ מ d) אינם מתחלקים במכנה. לכן d חייב להתחלק בו.נגדיר: 
עכשיו נציב:
מכיוון ש p ראשוני אז q חייב להיות שווה 1 (מספר ראשוני מתחלק בעצמו ובאחד)
ושוב, בגלל אותו נימוק:
הצלחנו לבטא את p כפונקציה של מספר טבעי b. (זו רק ההתחלה)
התבנית שיקבלנו אמנם מבטיחה ש p מקיים את המשוואה הנ"ל היא לא מבטיחה שהוא ראשוני.
ניתן לבדוק על כל איבר בסדרה הזו האם הוא ראשוני או לא, אבל זה ייקח הרבה זמן, במיוחד כאשר מדובר על מספרים גדולים.
נניח כי קיימים שני מספרים t, s השייכים לקבוצה p, ויש להם גורם ראשוני משותף r.
ה 3 לא מעניין אותנו כי r בטח לא מתחלק ב 3, כי כל איבר בקבוצה p לא מתחלק ב 3.
לכן k חייב להתחלק ב 3, וכאשר נחלק את שני האגפים ב 3 נקבל עדיין את אותה הצורה:
יש שתי אפשרויות: (שתיהן מתקיימות, k פה יציין 'מספר טבעי כלשהו' ולא אותו ה k ממקודם)
לכן אמ"מ (ניתן גם להוכיח הפוך) איבר כלשהו במקום c בסדרה p מתחלק ב r אז גם האיברים
יתחלקו בגורם ראשוני r.
אם באלגוריתם שלנו נעבור על כל האיברים ב p (שכבר חישבנו) נוכל בקלות לבדוק האם הם ראשוניים או לא.
כאשר נעבור על איבר במיקום i בקבוצה שלנו(והאיבר ראשוני) – נחלק את כל האיברים הבאים שיתחלקו ב p(i) כמו שהראינו לעיל:
אם מספר במיקום כלשהו השתנה זה אומר שהוא חולק איפשהו באלגוריתם שלנו ואם הוא חולק זה אומר שזה לא מספר ראשוני.
אם שמת לב למשהו מוזר לפני 3 שורות זה סימן שאתה עדיין עוקב ;-)
נכתב לעיל: "נוכל בקלות לבדוק האם הם ראשוניים או לא... איבר בקבוצה(והאיבר ראשוני)"
איך הגעתי למסקנה שהאיברים שאני רץ עליהם ראשוניים?
בעצם, בדרך הזו שאנו מחלקים כל איבר אחר בעל אותו גורם ראשוני, אנחנו מוציאים החוצה מרשימת הגורמים של האיבר את אותו גורם. כדי שכשנגיע לאיבר הוא יהיה ראשוני – אמור להיות לו גורם אחד שלא הוצא מרשימת הגורמים שלו.
כאשר הגורם f מקיים 
אז הגורם של p(b) הוצא ב
כאשר הגורם f מקיים 
אז הגורם הוצא מ p(b) ב 
כאשר הגורם f מקיים 
אז בהחלט יתכן כי לא הוצא הגורם f מ p(b) אך ממילא לא יתכן יותר מגורם אחד הגדול מ 2b לאיבר p(b) כי אם היו שניים אז הפונקציה הייתה אמורה להיות לפחות 
לסיכום, בדרך הנ"ל בה אנחנו מחלקים את כל האיברים בעלי אותו גורם אנחנו גורמים לכל האיברים להיות ראשוניים ולכן אין לבצע עליהם בדיקת ראשוניות. הבדיקה היחידה שכן נצטרך לעשות עליהם היא לבדוק האם לא חילקנו את האיבר אי פעם. זאת בקלות נוכל לעשות ע"י השוואה של האיבר לערך שהיינו מצפים שהוא יהיה.
קוד של פתרון החידה:
static void Main(string[] args) {
const long Lim = (long)1e+16; // limit of our search
List<long> cubicPrime = new List<long>((int)Math.Sqrt(Lim / 3) + 1); // creating list which contains the candidates to be cubic prime (3n^2+3n+1)
long candidate; // saving variable
cubicPrime.Add(0); // we want to start the array from cubicPrime[1] for comfortable, because we computed all with one-based-group
for (int i = 1; (candidate = Term(i)) < Lim; ++i)
{
cubicPrime.Add(candidate); //adding all the candidates
}
int CubicPrimeCounter = 0; //counter of how many cubic primes there are
for (int i = 1; i < cubicPrime.Count; ++i)
{
if (cubicPrime[i] == 1) continue; //if equal to 1 than it doesn't contain any new prime factor
candidate = Term(i);
if (cubicPrime[i] == candidate) // the candidate is really a prime, we haven't divided cubicPrime[i]
++CubicPrimeCounter; // a cubic prime is found
// dividing the next terms in the prime factor we've just found
candidate = cubicPrime[i];
for (int k = (int)((i + 1) / candidate + 1), index; (k * candidate - i - 1) < cubicPrime.Count; ++k)
{
index = (int)(k * candidate - i - 1);
do
cubicPrime[index] /= candidate;
while (cubicPrime[index] % candidate == 0);
}
for (int k = 1, index; (k * candidate + i) < cubicPrime.Count; ++k)
{
index = (int)(k * candidate + i);
do
cubicPrime[index] /= candidate;
while (cubicPrime[index] % candidate == 0);
}
}
Console.WriteLine(CubicPrimeCounter);
}
static long Term(long index)
{
return 3 * index * (index + 1) + 1;
}
