A lot of people believe that everything can and must be rationally explained, or at least that there is a very limited set of "weird" things on Earth without a rational explanation(e.g. miracles according to several different religions).
The fact that there are 300,000/up to a million people (see During the events of the Harry Potter series what is the total population of Wizards/Witches globally?) throughout the world performing "weird" things on a daily basis, without any rational explanation whatsoever, can definitely raise some eyebrows.
Moreover, there are relatively few occasions for Muggles to witness blatantly magical events and, in most cases, Obliviators step in and erase/modify the memories of the witnesses.
The average Muggle who tends to rationalize is led to think that magic doesn't exist because he/she has never witnessed an act of magic, and because history and science books (which are the basis of a Muggle education to understand how the world and the society work) haven't talked about magic.
Only Muggle parents of Hogwarts students can connect the news on their newspapers to their knowledge of the Wizarding world (I recall Hermione saying something like, "Even my parents are worried, and they are Muggles!").
Now, let us consider the Muggle PM before and after knowing the truth about magic.
Muggle PM, before knowing the truth
Like most Muggles, the PM is apparently a rationalist. He considers himself an educated man, and throughout his life he has seen the world with a seemingly consistent view, so that is able to explain most events witnessed by Muggles. Because of the International Statute of Secrecy, blatant acts of magic don't (usually) occur and, because of Occam's razor, the PM (like most Muggles) is led to think that there must be a rational, yet unknown, explanation to the occasional "weird" things he may witness.
Muggle PM, after knowing the truth
Former Prime Ministers usually remain influential political figures and the current PM wouldn't risk being made fun of by other Muggles (including well-known politicians he may need to keep in touch with). As an example, people could say
Look at him, he believes everything he's being told! Heck, he even believes that magic is real! (laughter ensues).
Therefore, the PM accepts the existence of the MoM, etc. without telling anyone in order to maintain political credibility.
In addition to that, you must remember what Fudge said to the Prime Minister(HBP):
It's live and let live.
The PM may think that it's better not to do things - like discussing about magic with other people - that may anger the MoM, and he may be right.
After all, when someone can get in your office, make people forget about scheduled calls, and transfigurate your teacup to a gerbil, you'd better do what he/she tells you to do.
In fact, I suspect enchantments exist that prohibit the Muggle PM from telling anyone about magic, and that (as NKCampbell suggests) Obliviators modify the memories of former PM's.
For all these reasons, at least as long as the Wizarding world doesn't interfere with Muggles, it is a wise move for the PM to not tell anyone about magic.
Another thing you need to consider is what would happen should the Muggle Prime Minister tell to the general public that wizards exist and that they do (or may) prove to be a threat for everyone.
First, the PM cannot provide any proof.
Yes, he talked with the MoM, but so what? Is there any recording of proof of the meeting? Probably not, because of fear and/or special enchantments.
Is there any proof that the PM did not talk to an insane person? No. Such an unexpected announcement would need at least some kind of proof, otherwise it may not be taken seriously.
What if Muggles did believe the PM? Since this information is completely unexpected and since most wizards live in Muggle areas, it would be similar to a sudden announcement of the outburst of a civil war, with additional confusion caused by not knowing the full extent of magic and its limitations.
I'm not a lawyer (or a politician or someone holding security clearances), but it seems to me that the reactions to this announcement would amount to a "serious(or even exceptional) damage to national security" (see https://www.law.cornell.edu/cfr/text/18/3a.11) and, as a result, this information should be at least classified as Secret or Top Secret. Since only the PM is told about it, this information may fall into the category of "things the PM/Head of State knows because of his office but must not discuss with anyone".
TL;DR. Most Muggles tend to rationalize and dismiss weird things they may witness.
The International Statute of Secrecy usually does a good job of hiding the existence of the wizarding world, so Muggles don't often encounter blatant acts of magic.
The PM doesn't tell anyone about magic because:
- he doesn't want to lose credibility
- he might be actually forbidden to tell anyone(because of special enchantments) and/or fears the reactions of the MoM
- this information would probably be considered as Top Secret classified, in the sense that its sudden announcement could possibly lead to chaos.