תורת החישוביות/סיבוכיות קולמוגורוב/יישומי אי-דחיסות/תרגילים

חסם פשוט על צפיפות המספרים הראשוניים

משפט המספרים הראשוניים אומר בקירוב שאם $p_i$ הוא המספר הראשוני ה-$i$, אז

$p_i\le i\ln (i).$

בעזרת סיבוכיות קולמוגורוב, אפשר להראות בקלות רבה מאד תוצאה מעט יותר חלשה, לפיה

$p_i\le i(\log (i{)}^2+O(1)).$

.

הוכח תוצאה זו בצורה הבאה. נניח ש-$m$ הוא מספר כלשהו, ו-$p_i$ הוא המספר הראשוני הגדול ביותר המחלק אותו. תאר את $m$ בצורה יעילה (רמז: אל תשתמש ב-$p_i$ אלא ב--$i$). הוסף את העובדה כי רוב המחרוזות אינן דחיסות במיוחד,והשתמש בה עבור הטבעיים.

תבנית:מוסתר