Sachverhalt: Sachverhalt: A. Der irakische Staatsangehörige A._, geb. 1973, reiste am 27. August 1998 illegal in die Schweiz ein, wo er am gleichen Tag ein Asylgesuch stellte. Am 13. Dezember 2000 lehnte das Bundesamt für Flüchtlinge dieses Gesuch ab und wies A._ weg. Mit Urteil vom 17. Januar 2002 wies die Schweizerische Asylrekurskommission eine dagegen erhobene Beschwerde ab. Am 30. Mai 2002 wies sie ebenfalls ein Revisionsgesuch ab. Mit Urteil vom 24. Oktober 2002 bestrafte das Bezirksgericht X._ A._ wegen einfacher Körperverletzung, Freiheitsberaubung, mehrfacher Ausnützung einer Notlage, sexueller Belästigung sowie wegen mehrfacher Widerhandlung gegen das Betäubungsmittelgesetz mit 18 Monaten Gefängnis bedingt bei einer Probezeit von zwei Jahren sowie mit einer bedingten Landesverweisung von fünf Jahren. Am 5. Februar 2002 liess sich A._ von seiner irakischen Ehefrau scheiden. Am 3. Dezember 2002 heiratete er die Schweizerin B._ und nahm deren Familiennamen an. In der Folge stellten die Ehegatten je ein Gesuch um Erteilung der Aufenthaltsbewilligung an A._. Mit Verfügung vom 29. August 2003 verweigerte die Fremdenpolizei des Kantons Graubünden die Erteilung einer Aufenthaltsbewilligung mit der Begründung, es handle sich um eine Ausländerrechtsehe und der Ehemann habe einen Ausweisungsgrund gesetzt. Am 5. Februar 2002 liess sich A._ von seiner irakischen Ehefrau scheiden. Am 3. Dezember 2002 heiratete er die Schweizerin B._ und nahm deren Familiennamen an. In der Folge stellten die Ehegatten je ein Gesuch um Erteilung der Aufenthaltsbewilligung an A._. Mit Verfügung vom 29. August 2003 verweigerte die Fremdenpolizei des Kantons Graubünden die Erteilung einer Aufenthaltsbewilligung mit der Begründung, es handle sich um eine Ausländerrechtsehe und der Ehemann habe einen Ausweisungsgrund gesetzt. B. Am 26. Januar 2004 wies das Justiz-, Polizei- und Sanitätsdepartement Graubünden eine dagegen erhobene Beschwerde ab. Dabei liess es den Vorwurf fallen, es liege eine Scheinehe vor, begründete die Bewilligungsverweigerung aber weiterhin mit der Straffälligkeit von A._. Mit Urteil vom 30. April 2004 wies das Verwaltungsgericht des Kantons Graubünden eine dagegen eingereichte Beschwerde ab. Mit Urteil vom 30. April 2004 wies das Verwaltungsgericht des Kantons Graubünden eine dagegen eingereichte Beschwerde ab. C. Mit selbst verfasster, als "Rekurs" bezeichneter Eingabe vom 24. Mai 2004 wandten sich Ursina und A._ an das Bundesgericht. Am 4. Juni 2004 reichten sie eine anwaltlich verfasste, als Verwaltungsgerichtsbeschwerde bezeichnete Rechtsschrift nach. Sie beantragen, das Urteil des Verwaltungsgerichts sei aufzuheben und es sei A._ die Aufenthaltsbewilligung zu erteilen; überdies sei die Beschwerde mit aufschiebender Wirkung zu versehen. Das Justiz-, Polizei- und Sanitätsdepartement Graubünden, das Verwaltungsgericht des Kantons Graubünden und das Bundesamt für Zuwanderung, Integration und Auswanderung schliessen auf Abweisung der Beschwerde. Das Justiz-, Polizei- und Sanitätsdepartement Graubünden, das Verwaltungsgericht des Kantons Graubünden und das Bundesamt für Zuwanderung, Integration und Auswanderung schliessen auf Abweisung der Beschwerde. D. Mit Verfügung vom 6. Juli 2004 hat das präsidierende Mitglied der II. öffentlichrechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung zuerkannt.