In the "page.tpl.php" of your custom theme (might not work if you use a contributed theme that makes override on "theme_links" core function or alter "$primary_links" variable) just do :
print theme('links', $primary_links, array('class' => 'yourclass'));
This just prints a "ul li" structure without wrapper. This is exactly what the "garland" default core theme actually does.
Check "garland" source code at line "50" (click "view source" in the page): https://api.drupal.org/api/drupal/themes!garland!page.tpl.php/6
More on theme_links: https://api.drupal.org/api/drupal/includes!theme.inc/function/theme_links/6