| The ruler or highest official in a country. In a monarchy the monarch is the head of state. In a republic the president is head of state. They are entitled to the 21-gun salute.
Anyone who is in any way subordinate to another is not a head of state, though the term is sometimes used loosely in the media to cover the leader of a country regardless of their position. A prime minister is not a head of state, nor is the governor general of a Commonwealth country. They minister to or advise or represent their head of state.
A prime minister is a head of government, not of state. All countries have both a head of state and a head of government, though the offices may be combined. The head of government is the one who actually leads the cabinet. Therefore there are several possible distributions of power:
Monarch as head of state, prime minister as head of government. All monarchies fit this pattern, except absolute monarchies, in which there is no formal government distinct from the sovereign's personal power.
The second pattern is president as head of state, prime minister as head of government. This is the commonest pattern worldwide; examples include Germany and France. However, in Germany (or Ireland or India) the president is a figurehead, a non-partisan figure widely respected as a senior statesman, whereas in France the president is an actively political figure who holds much real power, while his prime minister is only his deputy if they're on the same side. (If the prime minister is a political opponent, power is distributed.). The figurehead and power-wielder models are both common, figureheads usually in Europe and strong executive presidencies in former French Africa.
The third pattern is president as both head of state and head of government intrinsically combined in the same office. This is the United States model and is also common worldwide, e.g. post-apartheid South Africa.
Minor variations. Those countries such as Australia and Canada in which the Queen is head of state but is not resident, have a governor general who performs the duties of head of state within that country, including dealing with the country's prime minister and parliament.
Communist countries usually had a third position distinct from president and prime minister, namely general secretary of the Communist Party. This person was always the real ruler of the country, not either of the others.
Sometimes a president in a two-office system may act as their own prime minister. This doesn't happen in Europe but I have seen a few examples in Africa.
In military juntas, typically the junta head does not bear the title of President, but has some elegant variation on Provisional Chairperson of the Revolutionary Command Council for National Salvation (or whatever); but in practice they are received as a head of state, equivalent to a president.
In rare instances (Saudi Arabia springs to mind) the king may be their own prime minister.
Iran has both a president and a prime minister but uniquely also has a theocratic leader enshrined in their constitution as one of higher rank than the president: this is the post of rahbar or velayat-e-faqih. The first holder was Ayatollah Khomeini and his successor is the present one, Ayatollah Ali Khamenei. I don't know how he is treated in terms of international protocol.
Libya is perhaps unique in not having a head of state (as opposed to just not having one currently). Colonel Muammar Qaddafi holds no official post, but is looked up to as "leader of the revolution". | 
