Faits:
A. Par jugement du 25 septembre 2008, le Tribunal correctionnel de l'arrondissement de Lausanne a condamné X._, pour viol, contrainte sexuelle et tentative de contrainte sexuelle, à 3 ans de privation de liberté (sous déduction de 44 jours de détention préventive), dont 18 mois avec sursis pendant 5 ans.
Saisie d'un recours du Ministère public, qui concluait à une aggravation de la peine, la Cour de cassation pénale du Tribunal cantonal vaudois l'a rejeté par arrêt du 4 novembre 2008, confirmant le jugement qui lui était déféré.
B. Cet arrêt retient, en résumé, ce qui suit.
B.a En 1997 et entre mars 2004 et février 2006, X._ a commis à 5 reprises des violences sexuelles à l'égard de prostituées, soit:
- une contrainte sexuelle, sous la forme d'une sodomie, à l'encontre de A._;
- une tentative de contrainte sexuelle, sous la forme d'une tentative de sodomie, à l'encontre de B._;
- un viol, sous la forme d'une pénétration tant vaginale qu'anale, à l'encontre de C._;
- deux tentatives de contrainte sexuelle, sous la forme de deux tentatives de sodomie, à l'encontre de D._;
- un viol, sous la forme d'un rapport sexuel complet suivi d'une sodomie, à l'encontre de E._.
B.b En bref, les juges cantonaux ont estimé qu'une peine privative de liberté de 3 ans apparaissait adéquate au vu de la culpabilité de l'accusé, ajoutant qu'un sursis partiel ne serait pas possible au-delà de 3 ans et que le pronostic n'était pas défavorable.
C. Le Ministère public forme un recours en matière pénale au Tribunal fédéral, pour violation de l'<ref-law>. Il conclut à ce que l'intimé soit condamné à une peine privative de liberté de 5 ans, subsidiairement à l'annulation de l'arrêt attaqué et au renvoi de la cause à l'autorité cantonale pour nouvelle décision.
L'intimé conclut au rejet du recours. L'autorité cantonale a renoncé à déposer des observations.

Considérant en droit:
1. Le recourant soutient que la peine infligée à l'intimé est exagérément clémente. Il reproche notamment aux juges cantonaux d'avoir tenu compte, à décharge, du fait que l'intimé a agi dans le cadre de relations vénales avec des prostituées. Il observe par ailleurs que la peine prononcée n'excède que d'une année celle de 2 ans qui l'eût sans doute été dans l'hypothèse où un seul viol, voire une seule contrainte sexuelle consommée, aurait été commis. A l'appui de son argument, il se réfère aux arrêts du Tribunal fédéral 6B_547/2008 et 6B_771/2007.
1.1 L'<ref-law> prévoit que la peine doit être fixée d'après la culpabilité de l'auteur, en tenant compte des antécédents et de la situation personnelle de ce dernier ainsi que de l'effet de la peine sur son avenir. L'alinéa 2 de cette disposition énumère, de manière non limitative, une série de critères à prendre en considération pour déterminer la culpabilité de l'auteur. Ces critères correspondent à ceux qui devaient être pris en compte selon la jurisprudence relative à l'art. 63 aCP, à laquelle on peut se référer (<ref-ruling> consid. 2.1 p. 19; cf. aussi arrêt 6B_472/2007 et les arrêts cités).
Pour fixer la peine, le juge dispose d'un large pouvoir d'appréciation. Il y a toutefois violation du droit fédéral lorsque le juge sort du cadre légal, lorsqu'il fonde sa décision sur des critères étrangers à l'<ref-law>, lorsqu'il omet de prendre en considération des éléments prévus par cette disposition ou lorsqu'il abuse de son pouvoir d'appréciation en fixant une peine exagérément sévère ou excessivement clémente (<ref-ruling> consid. 2.1 p. 19/20 et les arrêts cités).
1.2 Les juges cantonaux ont admis que, par le tort qu'elles ont causé aux victimes et par leur répétition dans le temps, les infractions commises par l'intimé étaient objectivement graves. Ils ont constaté que sa responsabilité était entière et que, lors de la procédure, il n'avait guère exprimé de regrets et avait fortement minimisé ses actes. De leur raisonnement, il ressort par ailleurs que les agissements de l'intimé paraissent essentiellement s'expliquer par un désir d'assouvir à tout prix ses pulsions, au mépris de la liberté sexuelle d'autrui. A décharge, les juges cantonaux ont toutefois estimé qu'il y avait lieu de tenir compte du fait que les infractions perpétrées présentaient "la particularité d'avoir été commises dans le cadre de relations avec des prostituées". Ils ont également pris en considération le caractère fruste de l'intimé, son absence de formation et le fait que son épouse était restée au pays. Ils ont ajouté que, s'il avait usé de sa force physique pour parvenir à ses fins, celui-ci n'avait pas exercé de violences sous formes de gifles ou de coups, ni fait usage de menaces. Enfin, ils ont relevé que l'intimé n'avait jamais été condamné en Suisse, où il avait toujours travaillé, y bénéficiant d'un bon revenu qui lui permettait d'entretenir sa famille.
1.3 Le recourant conteste à juste titre la pertinence de certains critères pris en compte à décharge.
Il était certes justifié de prendre en considération le fait que l'intimé a agi dans le cadre de relations sexuelles initialement consenties. Il n'était en revanche pas admissible de tenir compte, en sa faveur, du fait que les actes reprochés ont été commis dans le cadre de relations avec des prostituées, dans la mesure où un tel raisonnement revient à admettre que ces actes seraient de moindre gravité et la faute de l'intimé de moindre importance, parce qu'il s'en est pris à des prostituées. La gravité d'un viol, respectivement d'une contrainte sexuelle, ne saurait être relativisée, motif pris du statut ou de la profession de la victime. Une prostituée est non moins en droit que toute autre personne de refuser un rapport sexuel ou une pratique sexuelle déterminée. La gravité de l'acte commis par celui qui la contraint à s'y soumettre, respectivement l'importance de la faute de ce dernier, ne s'en trouve en rien diminuée.
Il n'est pas non plus acceptable de relativiser la gravité d'un viol, respectivement d'une contrainte sexuelle, au motif que l'auteur n'a pas frappé ou blessé la victime, ni ne l'a menacée. Le fait que l'auteur, en raison des circonstances, n'ait pas eu à recourir à de tels moyens, mais ait pu se limiter à profiter de sa supériorité physique n'amoindrit pas sa faute.
Il s'ensuit que les juges cantonaux ne pouvaient tenir compte, à titre de facteurs atténuants, des éléments qui viennent d'être examinés.
1.4 Dans les cas ordinaires, le viol est passible d'une peine privative de liberté de 1 an à 10 ans et la contrainte sexuelle d'une peine privative de liberté de 10 ans au plus ou d'une peine pécuniaires (cf. art. 190 al. 1 et 189 al. 1 CP). En cas de concours d'infractions, la peine doit être aggravée conformément à l'<ref-law>.
L'intimé doit répondre de deux viols consommés, d'une contrainte sexuelle consommée et de trois tentatives de contrainte sexuelle. Il a ainsi porté atteinte, de manière grave et répétée, à la liberté et à l'intégrité sexuelles d'autrui, s'en prenant à cinq personnes. Sa responsabilité n'était en rien diminuée et il n'a guère manifesté de regrets de ses actes, qu'il a au contraire fortement minimisés. Son absence d'antécédents ne fait pas contre-poids à la pluralité et à la répétition des actes commis ainsi qu'à son attitude au cours de la procédure, qui dénote une faible prise de conscience de ses actes. Son caractère fruste et sa difficulté à contrôler ses pulsions, s'ils peuvent les expliquer, ne justifient pas ses agissements. Force est ainsi de constater que les éléments favorables à l'intimé sont des plus ténus, alors que maints éléments lui sont défavorables. Dans ces conditions, la peine de 3 ans de privation de liberté qui lui a été infligée, parce que manifestement insuffisante au regard de sa culpabilité, doit être qualifiée d'abusivement clémente.
2. Le recours doit ainsi être admis, l'arrêt attaqué annulé et la cause renvoyée à l'autorité cantonale pour qu'elle statue à nouveau sur la peine dans le sens des considérants.
L'intimé, qui succombe, devra supporter les frais (<ref-law>). Il n'y a pas lieu d'allouer des dépens à l'accusateur public qui obtient gain de cause (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis, l'arrêt attaqué annulé et la cause renvoyée à l'autorité cantonale pour nouvelle décision.
2. Les frais judiciaires, arrêtés à 2000 fr., sont mis à la charge de l'intimé.
3. Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton de Vaud, Cour de cassation pénale.
Lausanne, le 18 mai 2010
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: La Greffière:
Favre Angéloz