Faits :
A.
A._, ressortissant roumain né en 1968, est titulaire d'un diplôme de médecin, ainsi que d'un titre postgrade de médecin-praticien obtenus en Roumanie. L'Office fédéral de la santé publique a reconnu ceux-ci par décisions du 26 mai respectivement du 2 juin 2014.
En 2013, l'activité professionnelle de A._ avait fait l'objet de procédures civile et pénale en Roumanie. La procédure pénale avait trait à des " infractions de fraude, contrefaçon intellectuelle et usage de faux... pour avoir délivré plusieurs prescriptions en faux, qui, ultérieurement, par l'interméde des pharmacies... ont été présentées pour règlement à la Caisse de Sécurité Sociale du département Giurgiu, préjudiciant l'institution avec la somme totale de 3'012'449 lei "; l'intéressé a été mis en détention durant l'instruction de cette cause.
Le 14 janvier 2015, l'autorité compétente du canton de Fribourg a retiré l'autorisation de pratiquer, que ce soit à titre dépendant ou indépendant, qu'elle avait octroyée à A._ le 8 juillet 2014. Elle lui reprochait de ne pas posséder les connaissances, les compétences et l'expérience nécessaires à la pratique médicale en Suisse: il ne connaissait ni les législations fédérale et cantonale en matière d'obligations professionnelles et de droits des patients, ni les normes régissant l'organisation d'un cabinet médical (droit du travail et des assurances sociales en ce qui concerne les employés); en matière d'assurances sociales, il n'avait suivi qu'un cours sur Tarmed; de plus, ses connaissances et compétences dans le domaine des produits thérapeutiques étaient nettement insuffisantes.
Une demande d'autorisation de pratiquer lui a également été refusée par l'autorité compétente du canton de Berne le 10 avril 2015.
Le Service de la santé publique du canton de Vaud a autorisé l'intéressé à pratiquer d'une part en qualité de médecin dépendant auprès de B._ Sàrl, par décision du 21 août 2015, et d'autre part en qualité de médecin remplaçant dans un cabinet médical du 7 août 2017 au 30 juin 2018, par décision du 3 août 2017 (le remplacement a pris fin le 30 novembre 2017 [<ref-law>]).
Deux interdictions temporaires de pratiquer la médecine en France ont été confirmées le 4 janvier 2018 par la Chambre disciplinaire nationale de l'Ordre des médecins (ci-après: la Chambre disciplinaire française) : la première lui interdisait d'exercer durant un an, dont six mois avec sursis, pour s'être installé dans des cabinets médicaux, à trois reprises en 2013 et 2014, soit après avoir repris la patientèle et l'ameublement de ceux-ci, soit en s'associant dans un cabinet de groupe, puis les avoir quittés après quelques mois sans prévenir et sans rembourser les charges dues, les prêts obtenus de ses confrères et le salaire d'une secrétaire (<ref-law>); la seconde interdiction a été prononcée pour une durée de trois mois pour avoir indiqué dans un questionnaire rempli en vue de son inscription au tableau du Conseil départemental de Haute-Savoie qu'aucune procédure judiciaire ou disciplinaire n'était en cours, alors qu'une plainte avait été déposée à son encontre. En outre, l'Ordre des médecins du Conseil régional de Bretagne avait annulé, le 19 octobre 2016, l'inscription de l'intéressé au tableau des médecins opérée le 27 juillet précédent: cette autorité lui reprochait d'avoir tu le retrait de l'autorisation de pratiquer dans le canton de Fribourg, ainsi que l'existence de plaintes de patients relatives à des questions administratives mal gérées (non-délivrance de feuille de soins, absence de règlement par l'assurance maladie, etc.), de loyers de locaux professionnels pas acquittés, de sa mauvaise compréhension de la langue française et de connaissances insuffisantes de la pharmacopée.
Le 22 mars 2018, A._ a adressé au Département des finances et de la santé de la République et canton de Neuchâtel (ci-après: le Département de la santé) une demande d'autorisation de pratiquer la médecine en vue de reprendre un cabinet médical à C._. Le formulaire à remplir à cette occasion comportait la question "Avez-vous fait ou faites-vous l'objet d'une procédure pénale ou administrative? Si oui, veuillez joindre la décision finale, voire la décision d'ouverture de la procédure", à laquelle l'intéressé a répondu par la négative. A la question " Une demande d'autorisation de pratiquer a-t-elle été refusée par un autre canton ou pays? Si oui, dans quels cantons ou quels pays? ", A._ a coché la case " Non " et a ajouté " Pas d'autorisation sur canton de Fribourg ".
Après avoir instruit l'affaire et découvert les procédures susmentionnées dont A._ n'avait pas fait mention dans sa demande d'autorisation, l'autorité compétente l'a entendu. Puis, par décision du 29 juin 2018, le Chef du Département de la santé a refusé de lui accorder l'autorisation de pratiquer la médecine sous sa propre responsabilité.
Par décision du 27 juin 2018, le canton du Jura a également refusé de lui octroyer une telle autorisation (<ref-law>).
A._ exerce comme médecin généraliste indépendant depuis le 9 juillet 2018 en Belgique et est inscrit au tableau de l'Ordre des médecins de ce pays.
B.
Par arrêt du 30 novembre 2018, la Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel (ci-après: le Tribunal cantonal) a rejeté le recours de A._ à l'encontre de la décision du 29 juin 2018 du Chef du Département de la santé. Elle a en substance jugé que celui-ci avait eu un parcours professionnel instable, pas exempt de reproches et qu'il avait tu volontairement et à plusieurs reprises des éléments fondamentaux le concernant, ce qui n'était pas de nature à créer un climat de confiance avec les autorités compétentes. Outre qu'il n'avait jamais déposé un récent extrait du casier judiciaire roumain, il n'avait pas déclaré les procédures le concernant en France et à Fribourg; ces éléments et les nombreux manquements, tant envers les autorités que ses confrères et patients, démontraient qu'il n'était pas digne de confiance et ne présentait pas les garanties nécessaires à un exercice irréprochable de la profession.
C.
Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal, sous suite de frais et dépens, outre l'octroi de l'assistance judiciaire, de réformer l'arrêt du 30 novembre 2018 du Tribunal cantonal et de lui accorder l'autorisation de pratiquer; subsidiairement, de renvoyer la cause audit tribunal, voire au Département de la santé pour une nouvelle décision lui octroyant une telle autorisation.
Le Département de la justice, de la sécurité et de la culture de la République et canton de Neuchâtel, sur délégation du Chef du Département de la santé, ainsi que le Tribunal cantonal concluent au rejet du recours, sous suite de frais. L'Office fédéral de la santé publique a renoncé à déposer des observations.
A._ s'est encore prononcé par écriture du 5 mars 2019.

Considérant en droit :
1.
Le recours en matière de droit public, déposé en temps utile (art. 100 et 46 al. 1 let. c LTF) et en la forme prévue (<ref-law>) à l'encontre d'un arrêt final (<ref-law>) rendu, dans une cause de droit public (<ref-law>), par une autorité cantonale de dernière instance (art. 86 al. 1 let. d LTF) par l'intéressé qui a la qualité pour recourir (<ref-law>), est recevable.
Le recourant a fait parvenir une pièce nouvelle (extrait du casier judiciaire roumain daté du 5 février 2019) au Tribunal fédéral qui ne peut pas la prendre en considération (<ref-law>).
2.
Le litige porte sur le refus d'autoriser le recourant à pratiquer la médecine au motif que celui-ci n'est pas digne de confiance, au sens de l'art. 36 al. 1 let. b de la loi fédérale du 23 juin 2006 sur les professions médicales universitaires (loi sur les professions médicales, LPMéd; RS 811.11), et ne présente pas les garanties nécessaires à un exercice irréprochable de la profession.
3.
3.1. Selon le recourant, son droit à une décision motivée aurait été violé en ce que le Tribunal cantonal se serait contenté d'indiquer que les formations de courte durée suivies en 2016 et 2017 n'étaient pas suffisantes pour remédier aux lacunes constatées quant à la législation fédérale et cantonale pertinente pour l'exercice de sa profession, sans expliquer la raison de cette constatation.
3.2. Le droit d'être entendu, garanti par l'art. 29 al. 2 Cst., implique notamment pour l'autorité l'obligation de motiver sa décision. La motivation d'une décision est suffisante, au regard du droit d'être entendu, lorsque l'autorité mentionne, au moins brièvement, les motifs qui l'ont guidée et sur lesquels elle a fondé sa décision, de manière à ce que l'intéressé puisse se rendre compte de la portée de celle-ci et l'attaquer en connaissance de cause. Le juge n'a toutefois pas l'obligation d'exposer et de discuter tous les faits, moyens de preuve et griefs invoqués par les parties, mais peut se limiter à l'examen des questions décisives pour l'issue du litige (<ref-ruling> consid. 4.2 p. 157). La motivation peut d'ailleurs être implicite et résulter des différents considérants de la décision (<ref-ruling> consid. 3.2.1 p. 565; arrêt 2C_382/2017 du 13 décembre 2018 consid. 4.1).
3.3. L'autorité précédente a retenu la dissimulation, par l'intéressé, des procédures le concernant en France et à Fribourg, ainsi que ses nombreux manquements, tant envers les autorités que de ses confrères et patients. Elle en a conclu que ces éléments démontraient que celui-ci n'était pas digne de confiance et ne présentait pas les garanties nécessaires à un exercice irréprochable de la profession. Ce n'est qu'après cette conclusion qu'elle a ajouté que les brèves formations suivies en 2016 et 2017 n'étaient pas à même de combler les lacunes en matière de législation fédérale et cantonale (en matière d'obligations professionnelles, des droits des patients, de pharmacopée, du droit du travail et des assurances sociales). La question de la formation n'était donc pas décisive pour l'issue du litige et les juges précédents n'avaient pas à indiquer plus en détails la raison pour laquelle ces cours étaient insuffisants.
4.
Sous la rubrique " Faits ", le recourant présente sa propre version des faits, en complétant celle de l'arrêt attaqué. Il ne prétend toutefois pas que ceux-ci auraient été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law>; il ne cite au demeurant pas l'<ref-law>. Partant, le Tribunal fédéral statuera sur la base des faits constatés par l'autorité précédente (<ref-law>), sous réserve de ceux complétés d'office (<ref-law>).
5.
Le recourant se plaint d'une violation de l'<ref-law>. Il estime que c'est à tort que le Tribunal cantonal a retenu qu'il n'était pas digne de confiance; en outre, il posséderait les capacités personnelles et professionnelles nécessaires à l'exercice de sa profession.
5.1. Selon l'<ref-law>, l'exercice d'une profession médicale universitaire à titre indépendant requiert une autorisation du canton sur le territoire duquel la profession médicale est exercée.
Les conditions professionnelles et personnelles pour l'octroi de l'autorisation de pratiquer sont réglées exhaustivement à l'<ref-law> (<ref-ruling> consid. 3.2 p. 355). L'al. 1 dispose:
" 1 L'autorisation de pratiquer à titre d'activité économique privée, sous propre responsabilité professionnelle, est octroyée si le requérant:
a. est titulaire du diplôme fédéral correspondant;
b. est digne de confiance et présente, tant physiquement que psychiquement, les garanties nécessaires à un exercice irréprochable de la profession;
c. dispose des connaissances nécessaires dans une langue officielle du canton pour lequel l'autorisation est demandée. "
Le Message du 3 décembre 2004 concernant la loi fédérale sur les professions médicales universitaires (Loi sur les professions médicales, LPMéd) précise, en ce qui concerne l'<ref-law>, que le requérant doit être de bonne moralité et, de manière générale, digne de confiance (FF 2004 209 ad <ref-law>). Le terme " de manière générale " démontre que le comportement qui peut être pris en considération à cet égard n'est pas limité à celui que l'intéressé adopte dans l'exercice concret de son activité au quotidien (par exemple, les soins médicaux en tant que tels); il faut, néanmoins, qu'il y ait un rapport avec l'exercice d'une activité indépendante dans le domaine médical (arrêt 2C_853/2013 du 17 juin 2014 consid. 5.4 qui définit la notion de " digne de confiance "). En outre, le requérant ne doit pas seulement faire montre d'un caractère digne de confiance dans sa relation avec ses patients, mais également face aux autorités médicales (arrêts 2C_814/2018 du 29 mars 2019 consid. 4.2; 2C_853/2013 du 17 juin 2014 consid. 5.5 et les arrêts cités).
Le Tribunal fédéral a récemment jugé que celui qui omet de déclarer, dans le formulaire à remplir afin d'obtenir une autorisation de pratiquer à titre indépendant qui comporte une question relative à d'éventuelles procédures pénale ou administrative en cours à son encontre, une procédure administrative pendante à son encontre à l'étranger pour des faits liés à l'exercice de sa profession trompe l'autorité chargée d'évaluer ladite demande; une telle attitude ne pouvait pas être qualifiée de " digne de confiance " au sens de l'<ref-law> (arrêt 2C_814/2018 du 29 mars 2019 consid. 4.3).
5.2. En l'espèce, le recourant n'a pas mentionné, dans sa demande d'autorisation de pratiquer du 22 mars 2018, les procédures civile et pénale dont il avait fait/faisait l'objet en Roumanie. A cet égard, on relève qu'au regard de la question figurant sur le formulaire à remplir doivent non seulement être signalées les procédures closes, mais également celles qui sont pendantes lorsque la personne intéressée remplit la demande d'autorisation de pratiquer. De même, le recourant n'a pas fait état des deux interdictions temporaires de pratiquer la médecine en France, confirmées le 4 janvier 2018 par la Chambre disciplinaire française, à savoir une interdiction d'exercer durant un an, dont six mois avec sursis, et une interdiction d'exercer de trois mois. Il n'a pas non plus signalé l'annulation par l'Ordre des médecins du Conseil régional de Bretagne, le 19 octobre 2016, de son inscription au tableau des médecins opérée le 27 juillet précédent.
De plus, alors que le formulaire à remplir comportait la question " Une demande d'autorisation de pratiquer a-t-elle été refusée par un autre canton ou pays? Si oui, dans quels cantons ou quels pays? ", l'intéressé a coché la case " Non ". S'il a mentionné " Pas d'autorisation sur canton de Fribourg ", bien qu'ayant répondu par la négative à cette question, il a tu le refus d'autorisation de pratiquer prononcé à son égard, dans le canton de Berne, le 10 avril 2015.
Le point de savoir si l'intéressé avait déjà déposé sa demande d'autorisation dans le canton du Jura, qui a abouti au refus du 27 juin 2018, lorsqu'il a présenté celle ici en cause le 22 mars 2018 dans le canton de Neuchâtel (ce qui aurait pour conséquence un élément dissimulé de plus à la charge de celui-ci, puisqu'il devait annoncer une demande d'autorisation de pratiquer qui avait été présentée dans un autre canton) peut rester ouvert. En effet, les omissions susmentionnées suffisent à sceller le sort du grief.
Au regard des éléments qui précèdent, le recourant a trompé l'autorité chargée d'évaluer sa demande d'autorisation de pratiquer et, le cas échéant, de la lui octroyer. Comme susmentionné, une telle attitude ne peut pas être qualifiée de digne de confiance au sens de l'<ref-law>. Partant, la condition personnelle pour obtenir une autorisation de pratiquer à titre d'activité économique privée, sous propre responsabilité professionnelle, n'est pas remplie et celle-ci ne peut être accordée à l'intéressé. Le grief tiré de la violation de l'<ref-law> est rejeté.
6.
Les conditions de l'art. 36 al. 1 let. a à c LPMéd étant cumulatives, il n'est pas nécessaire de déterminer si les connaissances de français du recourant sont suffisantes pour l'exercice de son métier, comme il le prétend.
A cet égard, la violation du droit à une décision motivée (cf. consid. 3) que le recourant invoque à ce propos, tombe à faux. Dès lors que, comme dit précédemment, les conditions de l'art. 36 al. 1 let. a à c LPMéd sont cumulatives, le Tribunal cantonal n'avait pas à analyser la condition de l'art. 36 al. 1 let. c LPMéd dans son arrêt et, partant, pas à examiner les connaissances de français de l'intéressé.
7.
Selon le recourant, dès lors qu'une autorisation de pratiquer lui a été délivrée par le canton de Vaud au mois d'août 2015, il aurait dû être autorisé à exercer dans le canton de Neuchâtel en vertu de l'<ref-law>.
7.1. L'<ref-law> prévoit que toute personne titulaire d'une autorisation de pratiquer délivrée conformément à la loi sur les professions médicales remplit en principe les conditions requises pour l'octroi d'une autorisation dans un autre canton.
7.2. Il sied tout d'abord de relever que cette disposition ne donne pas un droit à l'octroi d'une autorisation dans un canton lorsqu'un premier a délivré un tel document à la personne concernée. En effet, même si celle-ci dispose d'une autorisation dans un canton, l'autorité compétente du second peut (certes, d'après le Message du 3 juillet 2013 concernant la modification de la loi sur les professions médicales (LPMéd [FF 2013 5583 ad art. 36]), seulement " exceptionnellement ") la lui refuser.
Le Service de la santé publique du canton de Vaud a délivré deux autorisations au recourant. La première, datant du 21 août 2015, constituait une autorisation de pratiquer en qualité de médecin dépendant. Or, avant la modification la loi fédérale sur les professions médicales, entrée en vigueur le 1er janvier 2018 (RO 2015 5081), ladite loi ne concernait que les indépendants (cf. <ref-law> dans sa teneur avant le 1er janvier 2018, qui, après avoir décrit le but de la loi, précise " Dans ce but, elle établit les règles régissant l'exercice des professions médicales universitaires à titre indépendant " [al. 3 let. e]). Dès lors, l'autorisation vaudoise susmentionnée n'a pas été délivrée sur la base de la loi fédérale sur les professions médicales. De plus, la validité de ce document était limitée, c'est-à-dire que le recourant pouvait exercer son activité uniquement auprès de B._ Sàrl.
A raison, le recourant ne se prévaut pas de la seconde autorisation, fournie le 3 août 2017, qui ne lui permettait d'exercer qu'en qualité de médecin remplaçant pour une durée déterminée (7 août 2017 au 30 juin 2018) dans un cabinet médical précis.
En conclusion, le recourant ne peut rien tirer de l'<ref-law>.
8.
8.1. Pour la première fois devant le Tribunal fédéral, le recourant se plaint de la violation de la liberté économique (art. 27 Cst.), ce qu'il est autorisé à faire (<ref-ruling> consid. 4.4.6 p. 158). Il invoque l'intérêt public prépondérant qui serait constitué par la sécurité des patients: il n'aurait jamais reçu de plaintes formelles de ceux-ci ni été sanctionné pour atteinte aux droits de patients. En outre, il met en avant son intérêt privé à exercer sa profession.
8.2. Ce grief doit être rejeté. D'une part, l'art. 27 al. 1 Cst. ne confère aucun droit à exercer la profession de médecin à titre d'activité économique privée sous propre responsabilité professionnelle, à savoir une profession libérale soumise à la surveillance de l'Etat, alors que les conditions légales pour y être autorisé ne sont pas réunies (arrêts 2P.268/2006 du 29 mars 2007 consid. 6; 2P.243/2000 du 14 mars 2001 consid. 1a/bb; <ref-ruling> consid. 2c p. 269 s.), étant précisé que la condition personnelle de l'<ref-law> n'a pas une valeur moindre que celle de la nécessité du diplôme fédéral (<ref-law>). D'autre part, ce moyen se confond avec celui de la violation du droit fédéral, qui a été correctement appliqué en l'espèce (cf. consid. 5).
9.
Il découle de ce qui précède que le recours est rejeté.
Succombant, le recourant doit supporter les frais judiciaires (<ref-law>). Le recours se révélant d'emblée dénué de chances de succès (<ref-ruling> consid. 1.2 p. 397), l'intéressé ne saurait bénéficier de l'assistance judiciaire (<ref-law>). Il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
La requête d'assistance judiciaire est rejetée.
3.
Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant.
4.
Le présent arrêt est communiqué aux mandataires du recourant, au Département des finances et de la santé (DFS) et au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, ainsi qu'à l'Office fédéral de la santé publique.
Lausanne, le 16 mai 2019
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
La Greffière : Jolidon