First, let me start off by saying this: Don't underestimate the value of telephoto for landscapes. While wide angle has generally been the primary choice for people who wish to photograph landscapes, the telephoto range (70-80mm and up) has a LOT to offer in the way of intriguing landscape compositions. That said...
Primes usually offer better quality, and can (sometimes) be lighter than their zoom counterparts. If you want the utmost in quality, a prime will probably serve you well. Keep in mind that a prime will limit your compositional freedom, and you will have to physically move your camera to reframe. You can also use copious amounts of post-process cropping, but you lose resolution that way, so its not particularly ideal unless you have megapixels to spare.
These days, zoom lenses are very well built, and utilize a variety of special lens elements to correct various optical aberrations like chromatic aberration and whatnot. I find it useful to have a variety of lenses on hand for my landscape photography. I am a Canon user, however there are similar lenses for Nikon users. My two primary lenses are my EF 16-35mm f/2.8 L II wide angle zoom, and my EF 100-400mm f/4.5-5.6 L IS USM telephoto zoom. These cover most (but not all) of my needs on most days. The telephoto triples as a landscape lens, a wildlife lens, and a birding lens. Excellent lens. Nikon has similar lenses, such as their 14-24mm ultrawide zoom and their 80-400mm telephoto zoom.
Between these two extremes, I also highly recommend some "normal" lenses. The standard 50mm is pretty much a given, as it is a great focal length that can be had for extremely cheap these days. If you really want to take prime lenses to the extreme, and really make your landscape photography stand out, I also recommend looking into tilt/shift lenses. Normal lenses provide one, maybe two controls: focus and zoom. A tilt/shift lens adds three more controls: tilt, shift, and rotation (-90 to +90 degrees, allowing you to control the plane of shift and tilt within a 180 degree rotation.) With these additional lens movements, you have creative control over your focal plane, which allows you much greater freedom over what parts of your scene are in-focus, and what parts are out of focus. For landscapes, you can either use this to easily bring your whole entire scene into focus without having to use an extremely small aperture, or use it to create non-planar focus in your scene (i.e. have one half of your scene out of focus from top to bottom, while the other half is in focus.)
Canon offers tilt/shift lenses, or TS-E lenses, in several varieties: 17mm, 24mm, 45mm, and 90mm. I believe that Nikon offers a couple tilt/shift lenses, however I am not sure what level of quality they offer. There are also a couple third party lens manufacturers who make tilt shift lenses for Nikon, including Hartbeli, Hartbeli & Zeiss, and a creative tilt/shift lens by LensBaby.
Regarding a cropped sensor, I think the best way to deal with that is simply apply the crop factor to the focal length. There are some general guidelines that can help you determine which focal length will be useful for particular types of photography. For Nikon, the crop factor is 1.5, so:
| FF Focal Length | Crop Factor Required
| | Focal Length
-------------------------------------------------------------------------
"Big" Landscape | 14mm - 24mm | 8mm - 16mm
"Close" Landscape | 24mm - 50mm | 16mm - 35mm
"Inside" or "Far" Landscape | 85mm - * | 55mm - *
-------------------------------------------------------------------------
Wildlife in Landscapes | 24mm - 50mm | 16mm - 35mm
Wildlife Portraits/Closeup | 200mm - 600mm | 135mm - 400mm
-------------------------------------------------------------------------
Birds Perching | 300mm - 800mm | 200mm - 550mm
Birds in Flight | 70mm - 500mm | 45mm - 350mm
Now, the above chart is based on my own experience with focal lengths, my own 450D, and a borrowed 5D with a few lenses. Namely, the 16-35mm zoom, a 50mm prime, an 85mm prime, a 100mm macro prime, a 100-400mm telephoto zoom, and a 50-550mm superzoom. Note that for birds in flight or any kind of wildlife in motion, the lenses I have used barely cut it. The Canon EF 100-400mm is capable of capturing birds in flight when there is good lighting, like daytime sunlight or early sunset light on a good summer day. The Sigma Bigma (50-500mm) did not fare well for birds in flight, however it does a pretty decent job for perching birds and rather still wildlife. I know you only mentioned landscapes, however I thought I would throw the rest in there, as telephoto lenses can be useful for both landscape and wildlife...and the two fields of photography are natural extensions of each other (no pun intended.)