یک مثال از کتاب پرهامی

مسئله تهیه لیستی از اعداد اول در فاصله تعریف شده برای عدد داده شده N>0 می باشد. 

[1..N]

یک الگوریتم ساده برای انجام اینکار استفاده از روش غربال   Eratosthenes می باشد. بدین صورت که با لیستی از اعداد به صورت 1,2,3,..,N  که به صورت یک بردار که با 00..1000 مقدار دهی شده است نمایش می دهیم. در هر گام  عدد بعدی m که علامتدار نشده است (عددی که بیت مربوطه اش در بردار برابر 0 است. ) اول است. با پیدا کردن این عدد، شروع به حذف مضارب این عدد که با m² شروع می شود، می کنیم. زمانی که m²>n شود محاسبات تمام می شود و تمام اعدادی که با 0 علامتگذاری شده اند اول هستند. 

شکل زیر گام های محاسبات را برای N=30 نشان می دهد. 

در شکل بالا پیاده سازی این الگوریتم در تک پردازنده دیده می شود. متغیر عدد اول جاری با عدد 2 مقدار دهی اولیه می شود و در گام های بعدی آخرین عدد اولی که تا به حال پیدا شده است را در این متغیر نگه داری می کنیم. برای هر عدد اولی که پیدا می کنیم متغیر index  با مقدار مربع این عدد مقدار دهی می شود. و سپس با مقدار عدد اول جاری افزایش می یابد تا تمام ضرایب این عدد را علامتگذاری کند. 

شکل زیر اولین راه حل ما برای اجرای موازی این الگوریتم با P پردازنده را نشان می دهد. لیست اعداد و عدد اول جاری (the current prime) را در یک حافظه اشتراکی ذخیره می کنیم. که برای همه پردازنده ها قابل دسترسی است. 

در این روش هر پردازنده که بیکار است به حافظه اشتراکی مراجعه کرده و عدد اول جاری را به روز می کند. و با استفاده از ایندکس این عدد از در میان لیست حرکت کرده و و مضارب این عدد اول را علامتگذاری می کند. 

در نتیجه این تقسیم کار به صورت خودکار انجام می شود. در شکل زیر فعالیت های یک پردازنده را در این روش شرح می دهد. برای n=1000 , p>=1  , p<= 3 

دقت کنید که در این روش حل موازی افزایش پردازنده ها بیشتر از 3 زمان محاسبات را کاهش نخواهد داد. زیرا کار پردازنده اول 500 استپ زمان نیاز خواهد داشت. 

تلاش بعدی ما با تقسیم داده کار می کند بدین صورت که بردار بیتی که نماینده n عدد صحیح هستند به p تا قطعه مساوی تقسیم می کنیم. که هر قطعه در یک حافظه خصوصی یک پردازنده ذخیره می شود. فرض می کنیم که P<= sqrt(n  به طوریکه هر عدد اولی که در لیست باقی خواهد ماند در قطعه مربوط به پردازنده اول نیز ضرایبی خواهد داشت. پردازنده اول نقش هماهنگ کننده خواهد داشت: این پردازنده مسئول پیدا کردن عدد اول بعدی و برودکست آن به پردازنده های دیگر است. و آن ها سپس شروع به علامت زدن ضرایب در زیر لیست خودشان هستند. کل زمان مربوط به این الگوریتم به دو بخش تقسیم می شود: زمان برودکست اعداد اول به پردازنده ها و زمان صرف شده توسط پردازنده های برای علامتگذاری اعداد درون لیست.