प्राइम-गिनती फ़ंक्शन पीआई (एक्स) x से अधिक नहीं होने वाले प्राइम्स की संख्या की गणना करता है, और सदियों से गणितज्ञों को आकर्षित करता है। अठारहवीं शताब्दी की शुरुआत में, एड्रियान-मैरी लीजेंड्रे ने एक सहायक फंक्शन फाई (एक्स, ए) का उपयोग करके एक फॉर्मूला दिया जो कि उन संख्याओं की गणना करता है जो पहले से अधिक प्राइम के साथ छेड़छाड़ नहीं करते हैं; उदाहरण के लिए, संख्या 1, 7, 11, 13, 17, 1 9, 23, 2 9, 31, 37, 41, 43, 47, 4 9 के लिए फाई (50,3) = 14. फाई फ़ंक्शन की गणना phi के रूप में की जा सकती है (एक्स, ए) = फाई (एक्स, ए -1) - फाई (एक्स/पी (ए), ए -1), जहां फाई (एक्स, 1) एक्स और पी (ए) से अधिक नहीं है अजीब पूर्णांक की संख्या है ए-वें प्राइम नंबर है (पी (1) = 2 से गिनती)।
function phi(x, a)
if (phi(x, a) is in cache)
return phi(x, a) from cache
if (a == 1)
return (x + 1) // 2
t := phi(x, a-1) - phi(x // p[a], a-1)
insert phi(x, a) = t in cache
return t
एक सरणी पी भंडार छोटे एक के लिए एक-वें प्रधानमंत्री, sieving द्वारा गणना की। कैश महत्वपूर्ण है; इसके बिना, रन टाइम घातीय होगा। दिए गए फाई, लीजेंड्रे का प्राइम-गिनती फॉर्मूला पीआई (एक्स) = फाई (एक्स, ए) + ए -1, जहां एक = पीआई (मंजिल (वर्ग (एक्स))) है। लीजेंड्रे ने पीआई (10^6) की गणना करने के लिए अपने फॉर्मूला का इस्तेमाल किया, लेकिन उन्होंने 78498 के सही उत्तर के बजाय 78526 की सूचना दी, जो गलत है, हालांकि, एक जटिल मैन्युअल गणना के लिए आश्चर्यजनक रूप से बंद था।
1950 के दशक में, डेरिक एच लेह्मर गिनती अभाज्य संख्या के लिए एक बेहतर एल्गोरिथ्म दिया:
function pi(x)
if (x < limit) return count(primes(x))
a := pi(root(x, 4)) # fourth root of x
b := pi(root(x, 2)) # square root of x
c := pi(root(x, 3)) # cube root of x
sum := phi(x,a) + (b+a-2) * (b-a+1)/2
for i from a+1 to b
w := n/p[i]
lim := pi(sqrt(w))
sum := sum - pi(w)
if (i <= c)
for j from i to lim
sum := sum - pi(w/p[j]) + j - 1
return sum
उदाहरण के लिए, अनुकरणीय (10^12) = 37607912018. यहां तक कि इन एल्गोरिदम के साथ, और उनके आधुनिक विविधताएँ और बहुत तेजी से कंप्यूटर, यह पीआई के बड़े मूल्यों की गणना करने के लिए बेहद थकाऊ रहता है; इस लेखन में, सबसे बड़ा ज्ञात मूल्य पीआई (10^24) = 18435599767349200867866 है।
एन-वें प्राइम की गणना करने के लिए इस एल्गोरिदम का उपयोग करने के लिए, प्राइम नंबर प्रमेय के लिए एक अनुशासन एन-वें प्राइम पी (एन) एन> 5 के लिए एन लॉग एन और एन (लॉग एन + लॉग लॉग एन) के बीच, इसलिए सीमाओं पर पीआई की गणना करें और एन-वें प्राइम को निर्धारित करने के लिए बायसेक्शन का उपयोग करें, सीमाएं बंद होने पर सिलाई करने के लिए स्विचिंग करें।
मैं my blog पर कई प्रविष्टियों में प्रमुख संख्याओं पर चर्चा करता हूं।
क्षमा करें, यह मैकडॉनल्ड्स नहीं है - आपके पास यहां अनुरोध नहीं हैं। आपके पास प्रश्न हैं सटीक प्रोग्रामिंग मुद्दों के बारे में ... कृपया [एफएक्यू] – ppeterka
पढ़ें यह सच नहीं है कि 'मंजिल (x/j) * j == x - (x% j) '। फिर आपके द्वारा लिंक किया गया सूत्र 'पीआई (एक्स) = (-1) + एसयूएम {जे = 3..एन} (((जे -2)!)% जे) '(?) बन जाता है। अगला मॉड्यूलर गुणा का उपयोग करें (यानी '5!% 7 == (((((2 * 3)% 7) * 4)% 7) * 5)% 7')। –
@ सेवरनकोज़क वे कहते हैं कि यह प्रोग्रामिंग समस्या प्रश्न नहीं है क्योंकि आपके प्रश्न में कोई कोड नहीं है। –