The concept of a prototypical melody has been proposed to characterize sets of similar musical segments in a composition. In musicology, the degree of importance associated with a prototypical melody is proportional to the number of musical segments similar to it. In this paper, a novel approach is developed to extract all the prototypical melodies in a musical work. Our approach considers each music segment as a prototypical melody candidate and utilizes edit distance to isolate a set of music segments that are similar to this candidate. To expedite the process, a lower bounding mechanism is used to estimate the number of similar musical segments for each candidate to eliminate impossible options. Furthermore, the approach is extended to facilitate the extraction of all prototypical melodies in a set of musical works. Analysis is carried out on a real data set, and the results indicate significantly improved performance in average response time relative to existing approaches.